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 vector 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:vector
Returns:long long
Method signature:long long firstOccurrence(vector prod)
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
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)2010, TopCoder, Inc. All rights reserved.