Min Steps to one using DP
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

Question

Min Steps to one using DP

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.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(1)Explanation:

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

Accepted Answer

Dynamic programming

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.

Space Complexity: O(n)Explanation:

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

Since we are using a ‘dp’ array to store recurring sub-problems, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

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

Since we are using recursion and for each case, we have 2 calls, but since we used a ‘dp’ array to hash the subproblems, the overall time complexity will be O(N).

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number given to us.

'''



def countStepsToOneHelper(n, dp):



    # Base condition

    if n == 1:

        return 0



    inf = int(1e9)



    # Base condition



    if n < 1:

        return inf



    # If we have already visited the state.

    if dp[n] != -1:

        return dp[n]



    # Recurring for 'N - 1'

    minusOne = 1 + countStepsToOneHelper(n - 1, dp)



    div2 = inf

    div3 = inf



    # If 'N' is divisible by 3, recurr for 'N/3'

    if n % 3 == 0:

        div3 = 1 + countStepsToOneHelper(n // 3, dp)



    # If 'N' is divisible by 2, recurr for 'N/2'



    if n % 2 == 0:

        div2 = 1 + countStepsToOneHelper(n // 2, dp)



    dp[n] = min(minusOne, div2)

    dp[n] = min(dp[n], div3)



    return dp[n]





def countStepsToOne(n):

    dp = [-1 for i in range(n + 1)]



    return countStepsToOneHelper(n, dp)

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number given to us.

*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution {



    private static int countStepsToOneHelper(int n, int[] dp) {



        // Base condition.

        if (n == 1) {

            return 0;

        }



        int inf = (int)1e9;



        // Base condition.

        if (n < 1) {

            return inf;

        }



        // If we have already visited the state.

        if (dp[n] != -1) {

            return dp[n];

        }



        // Recurring for 'N - 1'.

        int minusOne = 1 + countStepsToOneHelper(n - 1, dp);



        int div2 = inf, div3 = inf;



        // If 'N' is divisible by 3, recurr for 'N/3'.

        if (n % 3 == 0) {

            div3 = 1 + countStepsToOneHelper(n / 3, dp);

        }



        // If 'N' is divisible by 2, recurr for 'N/2'.

        if (n % 2 == 0) {

            div2 = 1 + countStepsToOneHelper(n / 2, dp);

        }



        dp[n] = Math.min(minusOne, div2);

        dp[n] = Math.min(dp[n], div3);



        return dp[n];

    }



    public static int countStepsToOne(int n) {

        int[] dp = new int[n + 1];

        Arrays.fill(dp, -1);



        return countStepsToOneHelper(n, dp);

    }

}

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where 'N' is the number given to us.

*/



int countStepsToOneHelper(int n, vector &dp) {



	// Base condition.

	if (n == 1) {

		return 0;

	}



	int inf = 1e9;



	// Base condition.

	if (n < 1) {

		return inf;

	}



	// If we have already visited the state.

	if (dp[n] != -1) {

		return dp[n];

	}



	// Recurring for 'N - 1'.

	int minusOne = 1 + countStepsToOneHelper(n - 1, dp);



	int div2 = inf, div3 = inf;



	// If 'N' is divisible by 3, recurr for 'N/3'.

	if (n % 3 == 0) {

		div3 = 1 + countStepsToOneHelper(n / 3, dp);

	}



	// If 'N' is divisible by 2, recurr for 'N/2'.

	if (n % 2 == 0) {

		div2 = 1 + countStepsToOneHelper(n / 2, dp);

	}



	return dp[n] = min({minusOne, div2, div3});

}



int countStepsToOne(int n) {

	vector dp(n + 1, -1);



	return countStepsToOneHelper(n, dp);

}

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:

For example:

Input format:

Output Format :

Note:

Constraints:

Top Google Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Google Software Developer