Min Steps to one

Posted: 6 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Try Problem