Min Steps to one

Easy
0/40
Average time to solve is 15m
profile
Contributed by
36 upvotes
Asked in companies
IBMAmazonSprinklr

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
4
10

Sample Output 1 :

2
3

Explanation of the Sample Input 1:

In the first test case, 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.

In the second test case, it will take 3 steps to reduce it to 1, i.e. first subtract 1, then divide by 3, two times. Therefore a total of 3 steps are required.

Sample Input 2 :

2
6
12

Sample Output 2 :

2
3
Hint

 Can we use recursion for all possible cases?

Approaches (2)
Using Recursion

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.
Time Complexity

O((3 ^ N)), Where ‘N’ is the number given to us.

 

Since we are using recursion and for each case, we have three calls, therefore the overall time complexity will be O(3 ^ N). 

Space Complexity

O(N), Where ‘N’ is the number given to us.


Since we are using recursion, a call stack up to height ‘N’ would be made. Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Min Steps to one
Full screen
Console