# 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,

is divided by both 2 and 3nRecur for possibilities

(n/3), (n/2), (n-1)is divided by only 3 but not by 2 thennRecur for possibilities

(n/3), (n-1)is divided by only 2 but not by 3 thennRecur for possibilities

(n/2), (n-1)is divided by only 3 but not by 2 thennRecur for possibilities

(n/3), (n-1)is not divisible by both 2 and 3nThen only recur for

(n-1)We can write all this with help of recursive function,

If you draw the recursion tree for

you will find many overlapping sub-problems. Hence, we need to store all the already computed sub-problems through memorization.f(10)C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: