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.
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 all combinations, 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.