Digit DP for Product of Digits

Revision en1, by vamaddur, 2017-07-13 22:51:35

Let P(x) be a function that returns the product of digits of x. For example P(935) = 9*3*5 = 135. Now let us define another function P_repeat(x):

int P_repeat(int x){
    if(x < 10) return x
    return P_repeat(P(x))
}

For a value v, ind the number of numbers x less than N such that P_repeat(_x_) = v.

How would I make a transition between states in a digit DP for this problem?

Please help, and thanks in advance!

Tags dynamic programming, math and programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English vamaddur 2017-07-14 08:21:02 33 Tiny change: 'vance!\n\n' -> 'vance!\n\nUPD: The bounds are N <= 10^13.\n'
en3 English vamaddur 2017-07-13 22:52:17 1 Tiny change: ' value v, ind the nu' -> ' value v, find the nu'
en2 English vamaddur 2017-07-13 22:52:03 2 Tiny change: ' P_repeat(_x_) = v.\n\n' -> ' P_repeat(x) = v.\n\n'
en1 English vamaddur 2017-07-13 22:51:35 480 Initial revision (published)