Problem Statement |
| | Given a positive integer N, let P(N) denote the product of all digits in the decimal representation of N. For example, P(4256) = 4 * 2 * 5 * 6 = 240, P(2112) = 2 * 1 * 1 * 2 = 4 and P(100) = 1 * 0 * 0 = 0.
Consider the infinite sequence S = (P(1), P(2), P(3), ...). Given a int[] prod containing exactly M elements, find the first occurrence of (prod[0], prod[1], ..., prod[M-1]) in S as a consecutive subsequence. In other words, return the smallest positive index X such that P(X + i) = prod[i] for all i between 0 and M-1, inclusive. The constraints will guarantee that at least one such X exists. |
| |
Definition |
| | | Class: | ProductsOfDigits | | Method: | firstOccurrence | | Parameters: | int[] | | Returns: | long | | Method signature: | long firstOccurrence(int[] prod) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | It can be shown that under the constraints of this problem, the return value will always fit within a 64-bit signed integer datatype. |
| |
Constraints |
| - | prod will contain between 1 and 50 elements, inclusive. |
| - | Each element of prod will be between 0 and 1,000,000,000, inclusive. |
| - | There will be at least one occurrence of (prod[0], ..., prod[M-1]) in S as a consecutive subsequence, where M is the number of elements in prod. |
| |
Examples |
| 0) | |
| | | Returns: 1 | | Since P(1) = 1, P(2) = 2, ..., P(5) = 5, we have that S starts with an occurrence of (1, 2, 3, 4, 5). |
|
|
| 1) | |
| | | Returns: 9 | | P(9) = 9, P(10) = 0, P(11) = 1. |
|
|
| 2) | |
| | | Returns: 100 | | All numbers between 100 and 103, inclusive, have a 0 in their decimal representations. |
|
|
| 3) | |
| | |
| 4) | |
| | {108864, 127008, 145152, 163296, 0, 22680, 45360, 68040, 90720} |
| Returns: 789946 | |
|
| 5) | |
| | |
| 6) | |
| | |