pinku22's blog

Tough puzzle help
By pinku22, history, 8 years ago, In English

I have attached the screenshot of the problem statement any help in coming up with the solution.

the link to the problem statement : https://www.hackerrank.com/contests/sears-onsite/challenges/tough-puzzle

http://mirror.codeforces.com/predownloaded/dc/3a/dc3a95cd31acc2b686bf505760140774ad84427b.png http://mirror.codeforces.com/predownloaded/49/4f/494f83b63edfc3713a93d927c2a7ad4931a0feac.png

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Next time take a photo with your phone.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

By writing small values of n or from a well known property you can deduce that f(n) is multiplication of two functions phi(n) and number_of_divisors(n).

Since product of digits can only contain 2,3,5 or 7 as primes. Also max_powers of these primes can only be 30,19,13,11. Just iterate on i,j,k,l = power of 2,3,5 and 7 resp in product of primes. Then the problem reduces to number of numbers <=n having product of digits = 2^i*3^j*5^k*7^l = X and multiply by f(X). This can be easily solved using digits DP — g(position to generate, power of 2, power of 3, power of 5, power of 7, zero_or_not, prefix_or_not) — for details see attached code.

Code — http://ideone.com/CZTJFo

Time Complexity = O(number of distinct product of digits*4) = O(2*2*30*19*13*11)

→ Reply