ProductsOfDigits
TCO10 Round 4 · 2010-04-11 · by ivan_metelsky
TCO10 Round 4 · 2010-04-11 · by ivan_metelsky · Dynamic Programming, Simple Math
Problem Statement
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 aint[] 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.
Consider the infinite sequence S = (P(1), P(2), P(3), ...). Given a
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
Submissions are judged against all 174 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ProductsOfDigits with a public method long long firstOccurrence(vector<int> prod) · 174 test cases · 2 s / 256 MB per case