Finding minimum operations

Given a number N (1<= N <= 10^9) Find minimum number of operations to reduce N to 1. The allowed operations being

  1. Division by 2
  2. Division by 3
  3. Subtracting 1

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 ?

1 Like

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.

2 Likes

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…

1 Like

@maverick_xiii . Please accept the solution so that the question could be closed.

1 Like

@maverick_xiii moreover, pls upvote the answer if you get satisfied

okay. Thank you.

//