# Min Steps to one

Posted: 6 Dec, 2020
Difficulty: Easy

## PROBLEM STATEMENT

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