Minimum steps to minimize n as per given condition
Given a number n, count minimum steps to minimize it to 1 performing the following operations:
- Operation1: If n is divisible by 2 then we may reduce n to n/2.
- Operation2: If n is divisible by 3 then you may reduce n to n/3.
- Operation3: Decrement n by 1.
Input:
Input is a single integer, n.
Output:
Output the minimum number of steps to minimize the number performing only the above operations.
Constraints:
1 <= N <= 10000
Example:
Test case 1:
Input:
N=10
Output:
Minimum number of steps needed: 3
Test case 2:
Input:
N=6
Output:
Minimum number of steps needed: 2
Explanation:
For the above test case,
N=10
N is not divisible by 3, but by 2
So,
10->5
Now % is again neither divisible by 3 nor 2
So, only option is to decrement
Hence
5->4
4 can be decremented to 2 by dividing by 2
4->2
2->1
So,
The conversion path will be
10->5->4->2->1
Total 4 steps
But is this the optimal one?
Answer is no
The optimal will be
10 converted to 9 by decrementing
10->9
9->3->1
So, total of 3 steps which is the minimum number
Hence answer would be 3
The above problem is a classic recursion example.
Like,
Recur for possibilities (n/3), (n/2), (n-1)
Recur for possibilities (n/3), (n-1)
Recur for possibilities (n/2), (n-1)
Recur for possibilities (n/3), (n-1)
Then only recur for (n-1)
We can write all this with help of recursive function,
If you draw the recursion tree for f(10) you will find many overlapping sub-problems. Hence, we need to store all the already computed sub-problems through memorization.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer