# Min Steps to one

Posted: 6 Dec, 2020

Difficulty: Easy

#### You are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.

#### You can perform any one of the following 3 steps:

```
1) Subtract 1 from it. (n = n - 1) ,
2) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).
```

#### For example:

```
Given:
‘N’ = 4, it will take 2 steps to reduce it to 1, i.e., first divide it by 2 giving 2 and then subtract 1, giving 1.
```

##### Input format:

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The following ‘T’ lines contain a single integer ‘N’, denoting the number given to us.
```

##### Output Format :

```
For each test case, You are supposed to return an integer that denotes the minimum steps it takes to reduce the number to 1.
```

##### Note:

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10 ^ 5
Time Limit: 1sec.
```

Approach 1

The idea is to use recursion to find all possible cases and then, out of them, choose the minimum.

The steps are as follows:

- We will use a helper function ‘countStepsToOneHelper’ to recur, it takes ‘N’ as the input and returns the minimum steps to reduce ‘N’ to 1.
- Base conditions are as follows:
- If ‘N’ is 1, return 0, denoting we found a valid combination of steps.
- If ‘N’ is less than 1, return ‘INF’, which is 10 ^ 9, which denotes we did not find a valid combination.

- Maintain 3 variables, ‘minusOne’, ‘div2’, ‘div3’, which denote the number of steps to convert ‘N’ to 1 if we subtract 1, divide by 2, divide by 3, respectively.
- Recur for ‘N-1’ and save in ‘minusOne’, and add 1 to it to denote we have taken a step.
- Similarly, If ‘N’ is divisible by ‘2’, recur for ‘N / 2’ and save in ‘div2’ and add 1 to denote we have taken a step.
- Similarly, If ‘N’ is divisible by ‘3’, recur for ‘N / 3’ and save in ‘div3’ and add 1 to denote we have taken a step.
- Return the minimum of ‘minusOne’, ‘div2’, and ‘div3’ as the final result.

Approach 2

The idea is to use recursion to find all possible cases and then, out of them, choose the minimum. As there are maximum ‘N’ states, we can use a ‘dp’ array to store the recurring sub-problems, where ‘dp[N]’ represents the minimum number of steps it takes to convert ‘N’ to 1.

The steps are as follows:

- We will use a helper function ‘countStepsToOneHelper’ to recur. It takes ‘N’, and ‘dp’ as the input and returns the minimum steps to reduce ‘N’ to 1.
- Base conditions are as follows:
- If ‘N’ is 1, return 0, denoting we found a valid combination of steps.
- If ‘N’ is less than 1, return ‘INF’, which is 10 ^ 9, which denotes we did not find a valid combination.

- If we have already visited this state, return ‘dp[N]’.
- Maintain 3 variables, ‘minusOne’, ‘div2’, ‘div3’, which denote the number of steps to convert ‘N’ to 1 if we subtract 1, divide by 2, divide by 3, respectively.
- Recur for ‘N-1’ and save in ‘minusOne’, and add 1 to it to denote we have taken a step.
- Similarly, If ‘N’ is divisible by ‘2’, recur for ‘N / 2’ and save in ‘div2’ and add 1 to denote we have taken a step.
- Similarly, If ‘N’ is divisible by ‘3’, recur for ‘N / 3’ and save in ‘div3’ and add 1 to denote we have taken a step.
- Save the minimum of ‘minusOne’, ‘div2’, and ‘div3’ in ‘dp[N]’ to cache the given state.
- Return the minimum of ‘minusOne’, ‘div2’, and ‘div3’ as the final result.