TopCoder problem "ProductsOfDigits" used in TCO10 Round 4 (Division I Level Two)



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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11015

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14282&pm=11015

Writer:

ivan_metelsky

Testers:

PabloGilberto , zhuzeyuan

Problem categories:

Dynamic Programming, Simple Math