ProductsOfDigits | Topcoder Archive

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

```
{1, 2, 3, 4, 5}
```
```
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).
```
{9, 0, 1}
```
```
Returns: 9
```
P(9) = 9, P(10) = 0, P(11) = 1.
```
{0, 0, 0, 0}
```
```
Returns: 100
```
All numbers between 100 and 103, inclusive, have a 0 in their decimal representations.
```
{288}
```
```
Returns: 489
```
4 * 8 * 9 = 288.

{108864, 127008, 145152, 163296, 0, 22680, 45360, 68040, 90720}

Returns: 789946

```
{1}
```
```
Returns: 1
```
```
{0, 1, 2, 3, 4, 5}
```
```
Returns: 10
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.