Problem :ADADIG I am trying to solve this , my Approach is: For a given N : 1)If it is prime —> if single digit return 1 else return 0

2)else factorize N and find all combinations of its factor and add 1s to make the digital sum equal to be N and find all permutations of it and add them all and return this. for step 2 , I am unable to figure out How do I do that efficiently?

I really really enjoyed the problem! :)

OK, the solution I did is essentially the same you described.

N. If it has a prime factors > 9, then there's no solution. Otherwise, it will be a number of the form 2^{a}* 3^{b}* 5^{c}* 7^{d}. Any number with digital productNwill havecdigits 5 andddigits 7, but the other digits are combinations of primes 2 and 3, so they're a bit trickier.^{2}, 6 = 2 * 3, 8 = 2^{3}and 9 = 3^{2}, but since there can't that many digits, we can just try all combinations for numbers of digits 2, 3, 4, 6, 8 and 9. There can't be more than 18 digits 2 because 2^{19}> 3 * 10^{5}. Similarly, there can't be more than 11 digits 3, etc..kdigits of some number to an already existing number ofddigits, we have ways to do so. After adding all digits, we will have a number with sums, so we have to fill it withn-sdigits 1. Again, we use combinatorics, if we haveddigits already andoones, we have to distribute the ones.Awesome explanation ,but can there be a better approach if not to try all combinations?

You can do some pruning to consider less combinations of mixing 2's with 3's, but even if you try

allcombinations, including those that exceed the amount of primes you have and those that don't use all of them, there will be only 18 * 11 * 9 * 7 * 6 * 5 = 374220, so trying to make it more efficient is not worth it in my opinion.