Last Updated: 6 Dec, 2020
Min Steps to one
Easy
Asked in companies
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.
Approaches
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.
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.