Given a number N (1<= N <= 10^9) Find minimum number of operations to reduce N to 1. The allowed operations being
All intermediate values of N should also be integers. I have tried dynamic programming approach, but it consumes more than 3 seconds. Can anyone suggest a fast algorithm for this problem ?
As the number is in the range of integers the maximum no of moves to reach 1 can never exceed 32. So it can be done by precomputing the values dynamically upto 10^7 or so. And then for the rest of the numbers doing BFS i.e. starting from input N going all possibilities step by step and exploring all the possibilities up-to some known number which has already been precomputed and then taking the minimum moves as the answer.
If BFS is going to explore all possibilities from 10^7 to 10^9, then don’t you think it will be as slow as the DP approach ?
No, it won’t be slow as there can never be more than 32 steps in total. So many redundant cases can be removed in such a way. E.g. for subtracting 1 from each number will go to at max depth of 32 and then get rejected. If at any step we are going to divide by 2 then at max it would take 6 steps to reach the precomputed values and so on…
okay. Thank you.