Find the minimum no of steps to reduce a number n to 0 using any of the following 2 operations:
1)Decrement number n by 1.
2)Determine a != 1 and b != 1 such that n=a*b and reduce n to max(a,b).
please help me with the logic and code.
for ex:for n=9, ans is 4.
9->3->2->1->0
I guess this can be done using dynamic programming.
Suppose the input is n.
then the answer has to be min(1+dp[n-1], 1 + dp[max(a,b)]) where dp[i] is the answer to n =i. You will have to write the base case for some of the initial cases. This cannot be performed for prime inputs though. For when n is prime, you cannot perform dp[max(a,b)]. So, the answer will have to be 1+ dp[n-1].
Would you mind providing the link to the question?
Looks like basically the same question as this one:
thanks