Minimum Steps to One Problem

Problem statement

On a positive integer, you can perform any one of the following 3 steps:

1. Subtract 1 from it.

2. If it is divisible by 2, divide by 2.

3. If it is divisible by 3, divide by 3.

Given a positive integer n, find the minimum number of steps that takes n to 1.

Wait a second!! You might be thinking that this is a pretty simple problem. One can think of greedily choosing the step that makes n as low as possible and continues the same till it reaches 1. If you observe carefully, the greedy strategy doesn’t work here.

Let us take n = 10. If we use the Greedy approach, we get the following steps:

• Step 1: 10 / 2 = 5
• Step 2: 5 - 1 = 4
• Step 3: 4 / 2 = 2
• Step 4: 2 / 2 = 1

So the total number of steps required is 4. But the optimal way is this:

• Step 1: 10 - 1 = 9
• Step 2: 9 / 3 = 3
• Step 3: 3 / 3 = 1

Hence, the total number of steps must be 3. We need to try out all possible steps that we can make for each possible value of n that we encounter and choose the minimum of these possibilities.

Thus, this is not a Greedy problem.