Minimum steps to minimize n as per given condition

20 October 2023

Given a number n, count minimum steps to minimize it to 1 according to the following criteria:

If n is divisible by 2 then we may reduce n to n/2.
If n is divisible by 3 then you may reduce n to n/3.
Decrement n by 1.

Examples:

Input : n = 10
Output : 3

Input : 6
Output : 2

Greedy Approach (Doesn’t work always) :

As per greedy approach we may choose the step that makes n as low as possible and continue the same, till it reaches 1.

while ( n > 1)
{
    if (n % 3 == 0)
        n /= 3;    
    else if (n % 2 == 0)
        n /= 2;
    else
        n--;
    steps++;
}

If we observe carefully, the greedy strategy doesn’t work here.
Eg: Given n = 10 , Greedy –> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ).
But the optimal way is –> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ).
So, we must think of a dynamic approach for optimal solution.

Dynamic Approach:
For finding minimum steps we have three possibilities for n and they are:

f(n) = 1 + f(n-1)
f(n) = 1 + f(n/2) // if n is divisible by 2
f(n) = 1 + f(n/3) // if n is divisible by 3

Below is memoization based implementation of above recursive formula.

C++

// CPP program to minimize n to 1 by given 
// rule in minimum steps 
#include <bits/stdc++.h> 
using namespace std; 
  
// function to calculate min steps 
int getMinSteps(int n, int *memo) 
{ 
    // base case 
    if (n == 1) 
       return 0; 
    if (memo[n] != -1) 
       return memo[n]; 
  
    // store temp value for n as min( f(n-1), 
    // f(n/2), f(n/3)) +1 
    int res = getMinSteps(n-1, memo); 
  
    if (n%2 == 0) 
        res = min(res, getMinSteps(n/2, memo)); 
    if (n%3 == 0) 
        res = min(res, getMinSteps(n/3, memo)); 
  
    // store memo[n] and return 
    memo[n] = 1 + res; 
    return memo[n]; 
} 
  
// This function mainly initializes memo[] and 
// calls getMinSteps(n, memo) 
int getMinSteps(int n) 
{ 
    int memo[n+1]; 
  
    // initialize memoized array 
    for (int i=0; i<=n; i++) 
        memo[i] = -1; 
  
    return  getMinSteps(n, memo); 
} 
  
// driver program 
int main() 
{ 
    int n = 10; 
    cout << getMinSteps(n); 
    return 0; 
} 

Java

// Java program to minimize n to 1  
// by given rule in minimum steps 
import java.io.*; 
class GFG { 
  
// function to calculate min steps 
static int getMinSteps(int n, int memo[]) 
{ 
    // base case 
    if (n == 1) 
    return 0; 
    if (memo[n] != -1) 
    return memo[n]; 
  
    // store temp value for 
    // n as min( f(n-1), 
    // f(n/2), f(n/3)) +1 
    int res = getMinSteps(n - 1, memo); 
  
    if (n % 2 == 0) 
        res = Math.min(res,  
              getMinSteps(n / 2, memo)); 
    if (n % 3 == 0) 
        res = Math.min(res,  
               getMinSteps(n / 3, memo)); 
  
    // store memo[n] and return 
    memo[n] = 1 + res; 
    return memo[n]; 
} 
  
// This function mainly 
// initializes memo[] and 
// calls getMinSteps(n, memo) 
static int getMinSteps(int n) 
{ 
    int memo[] = new int[n + 1]; 
  
    // initialize memoized array 
    for (int i = 0; i <= n; i++) 
        memo[i] = -1; 
  
    return getMinSteps(n, memo); 
} 
  
    // Driver Code 
    public static void main (String[] args)  
    { 
        int n = 10; 
        System.out.println(getMinSteps(n)); 
    } 
} 
  
// This code is contributed by anuj_67. 

Python3

# Python program to minimize 
# n to 1 by given 
# rule in minimum steps 
  
# function to calculate min steps 
def getMinSteps(n, memo): 
  
    # base case 
    if (n == 1): 
        return 0
    if (memo[n] != -1): 
        return memo[n] 
  
    # store temp value for n as min(f(n-1), 
    # f(n//2), f(n//3)) + 1 
    res = getMinSteps(n-1, memo) 
  
    if (n%2 == 0): 
        res = min(res, getMinSteps(n//2, memo)) 
    if (n%3 == 0): 
        res = min(res, getMinSteps(n//3, memo)) 
  
    # store memo[n] and return 
    memo[n] = 1 + res 
    return memo[n] 
  
# This function mainly 
# initializes memo[] and 
# calls getMinSteps(n, memo) 
def getsMinSteps(n): 
  
    memo = [0 for i in range(n+1)] 
  
    # initialize memoized array 
    for i in range(n+1): 
        memo[i] = -1
  
    return getMinSteps(n, memo) 
  
# driver program 
n = 10
print(getsMinSteps(n)) 
  
# This code is contributed by Soumen Ghosh.    

C#

// C# program to minimize n to 1  
// by given rule in minimum steps 
using System; 
  
class GFG { 
  
    // function to calculate min steps 
    static int getMinSteps(int n, int []memo) 
    { 
        // base case 
        if (n == 1) 
            return 0; 
        if (memo[n] != -1) 
            return memo[n]; 
      
        // store temp value for 
        // n as min( f(n-1), 
        // f(n/2), f(n/3)) +1 
        int res = getMinSteps(n - 1, memo); 
      
        if (n % 2 == 0) 
            res = Math.Min(res,  
                getMinSteps(n / 2, memo)); 
        if (n % 3 == 0) 
            res = Math.Min(res,  
                getMinSteps(n / 3, memo)); 
      
        // store memo[n] and return 
        memo[n] = 1 + res; 
          
        return memo[n]; 
    } 
      
    // This function mainly 
    // initializes memo[] and 
    // calls getMinSteps(n, memo) 
    static int getMinSteps(int n) 
    { 
        int []memo = new int[n + 1]; 
      
        // initialize memoized array 
        for (int i = 0; i <= n; i++) 
            memo[i] = -1; 
      
        return getMinSteps(n, memo); 
    } 
  
    // Driver Code 
    public static void Main ()  
    { 
        int n = 10; 
        Console.WriteLine(getMinSteps(n)); 
    } 
} 
  
// This code is contributed by anuj_67. 

PHP

<?php 
// PHP program to minimize n to 1 by 
// given rule in minimum steps 
  
// function to calculate min steps 
function getMinSteps( $n, $memo) 
{ 
      
    // base case 
    if ($n == 1) 
        return 0; 
          
    if ($memo[$n] != -1) 
        return $memo[$n]; 
  
    // store temp value for n 
    // as min( f(n-1), 
    // f(n/2), f(n/3)) +1 
    $res = getMinSteps($n - 1, $memo); 
  
    if ($n % 2 == 0) 
        $res = min($res, getMinSteps($n / 2, $memo)); 
    if ($n % 3 == 0) 
        $res = min($res, getMinSteps($n / 3, $memo)); 
  
    // store memo[n] and return 
    $memo[$n] = 1 + $res; 
    return $memo[$n]; 
} 
  
// This function mainly initializes 
// memo[] and calls getMinSteps(n, memo) 
function g_etMinSteps( $n) 
{ 
    $memo= array(); 
  
    // initialize memoized array 
    for($i = 0; $i <= $n; $i++) 
        $memo[$i] = -1; 
  
    return getMinSteps($n, $memo); 
} 
  
    // Driver Code 
    $n = 10; 
    echo g_etMinSteps($n); 
  
// This code is contributed by anuj_67. 
?> 

Javascript

<script> 
// javascript program to minimize n to 1  
// by given rule in minimum steps 
  
    // function to calculate min steps 
    function getMinSteps(n , memo) 
    { 
      
        // base case 
        if (n == 1) 
            return 0; 
        if (memo[n] != -1) 
            return memo[n]; 
  
        // store temp value for 
        // n as min( f(n-1), 
        // f(n/2), f(n/3)) +1 
        var res = getMinSteps(n - 1, memo); 
  
        if (n % 2 == 0) 
            res = Math.min(res, getMinSteps(n / 2, memo)); 
        if (n % 3 == 0) 
            res = Math.min(res, getMinSteps(n / 3, memo)); 
  
        // store memo[n] and return 
        memo[n] = 1 + res; 
        return memo[n]; 
    } 
  
    // This function mainly 
    // initializes memo and 
    // calls getMinSteps(n, memo) 
    function getMinStep(n) { 
        var memo = Array(n + 1).fill(0); 
  
        // initialize memoized array 
        for (var i = 0; i <= n; i++) 
            memo[i] = -1; 
  
        return getMinSteps(n, memo); 
    } 
  
    // Driver Code 
        var n = 10; 
        document.write(getMinStep(n)); 
          
// This code is contributed by Rajput-Ji  
</script> 

Output

Time Complexity: O(n), as there will be n unique calls.

Space Complexity: O(n)

Below is a tabulation based solution :

C++

#include <bits/stdc++.h>  
using namespace std;  
  
int getMinSteps(int n)  
{  
    int table[n+1];  
    table[1]=0; 
    for (int i=2; i<=n; i++)  
    {  
    if (!(i%2) && (i%3))  
        table[i] = 1+min(table[i-1], table[i/2]);  
    else if (!(i%3) && (i%2)) 
        table[i] = 1+min(table[i-1], table[i/3]);  
    else if(!(i%2) && !(i%3)) 
        table[i] = 1+min(table[i-1],min(table[i/2],table[i/3]));  
    else
        table[i] =1+table[i-1]; 
    } 
    return table[n];  
}  
  
// driver program  
int main()  
{  
    int n = 14;  
    cout << getMinSteps(n);  
    return 0;  
}  

Java

// A tabulation based 
// solution in Java 
import java.io.*; 
  
class GFG { 
    static int getMinSteps(int n) 
    { 
        int[] dp = new int[n + 1]; 
  
        dp[1] = 0; 
  
        for (int i = 2; i <= n; i++) { 
            int min = dp[i - 1]; 
  
            if (i % 2 == 0) { 
                min = Math.min(min, dp[i / 2]); 
            } 
            if (i % 3 == 0) { 
                min = Math.min(min, dp[i / 3]); 
            } 
            dp[i] = min + 1; 
        } 
  
        return dp[n]; 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int n = 14; 
        System.out.print(getMinSteps(n)); 
    } 
} 
  
// This code is contributed 
// by anmol_sharma.

Python3

# A tabulation based solution in Python3  
  
def getMinSteps(n) : 
      
    table = [0] * (n + 1)  
      
    for i in range(n + 1) : 
        table[i] = n-i 
          
    for i in range(n, 0, -1) : 
          
        if (not(i%2)) : 
            table[i//2] = min(table[i]+1, table[i//2]) 
              
        if (not(i%3)) : 
            table[i//3] = min(table[i]+1, table[i//3]) 
              
    return table[1] 
  
  
# driver program  
if __name__ == "__main__" : 
  
    n = 14
    print(getMinSteps(n)) 
      
# This code is contributed by Ryuga 

C#

// A tabulation based  
// solution in C# 
using System; 
  
class GFG  
{ 
static int getMinSteps(int n) 
{ 
    int []table = new int[n + 1]; 
    for (int i = 0; i <= n; i++) 
        table[i] = n - i; 
    for (int i = n; i >= 1; i--) 
    { 
    if (!(i % 2 > 0)) 
        table[i / 2] = Math.Min(table[i] + 1,  
                                table[i / 2]); 
    if (!(i % 3 > 0)) 
        table[i / 3] = Math.Min(table[i] + 1,  
                                table[i / 3]); 
    } 
    return table[1]; 
} 
  
// Driver Code 
public static void Main () 
{ 
    int n = 10; 
    Console.WriteLine(getMinSteps(n)); 
} 
} 
  
// This code is contributed  
// by anuj_67. 

PHP

<?php 
// A tabulation based solution in PHP 
  
function getMinSteps( $n) 
{ 
    $table = array(); 
    for ($i = 0; $i <= $n; $i++) 
        $table[$i] = $n - $i; 
    for ($i = $n; $i >= 1; $i--) 
    { 
        if (!($i % 2)) 
            $table[$i / 2] = min($table[$i] +  
                          1, $table[$i / 2]); 
        if (!($i % 3)) 
            $table[$i / 3] = min($table[$i] +  
                          1, $table[$i / 3]); 
    } 
    return $table[1]; 
} 
  
    // Driver Code 
    $n = 10; 
    echo getMinSteps($n); 
  
// This code is contributed by anuj_67. 
?> 

Javascript

<script> 
  
    // A tabulation based solution in Javascript 
      
    function getMinSteps(n) 
    { 
        let table = new Array(n+1); 
        table.fill(0); 
        table[1]=0; 
        for (let i=2; i<=n; i++) 
        { 
          if (!(i%2) && (i%3)) 
              table[i] = 1+Math.min(table[i-1], table[i/2]); 
          else if (!(i%3) && (i%2)) 
              table[i] = 1+Math.min(table[i-1], table[i/3]); 
          else if(!(i%2) && !(i%3)) 
              table[i] = 1+Math.min(table[i-1], 
              Math.min(table[i/2],table[i/3])); 
          else
              table[i] =1+table[i-1]; 
        } 
        return table[n] + 1; 
    } 
      
    let n = 10; 
    document.write(getMinSteps(n)); 
      
</script>

Output

Time Complexity: O(n), as there will be n unique calls.

Space Complexity: O(n)

Using recursion:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
int getMinSteps(int n) 
{ 
    // If n is equal to 1 
    if (n == 1) 
        return 0; 
  
    int sub = INT_MAX; 
    int div2 = INT_MAX; 
    int div3 = INT_MAX; 
    sub = getMinSteps(n - 1); 
  
    if (n % 2 == 0) 
        div2 = getMinSteps(n / 2); 
  
    if (n % 3 == 0) 
        div3 = getMinSteps(n / 3); 
  
    return 1 + min(sub, min(div2, div3)); 
} 
  
// Driver code 
int main() 
{ 
    int n = 10; 
  
    // Function Call 
    cout << (getMinSteps(n)); 
    
} 
  
// This code is contributed by Potta Lokesh

Java

// Java program for the above program 
import java.io.*; 
  
class GFG { 
    public static int getMinSteps(int n) 
    { 
        // If n is equal to 1 
        if (n == 1) 
            return 0; 
        
        int sub = Integer.MAX_VALUE; 
        int div2 = Integer.MAX_VALUE; 
        int div3 = Integer.MAX_VALUE; 
        sub = getMinSteps(n - 1); 
        
        if (n % 2 == 0) 
            div2 = getMinSteps(n / 2); 
        
        if (n % 3 == 0) 
            div3 = getMinSteps(n / 3); 
        
        return 1 + Math.min(sub, Math.min(div2, div3)); 
    } 
    
    // Driver Code 
    public static void main(String[] args) 
    { 
        int n = 10; 
        
        // Function Call 
        System.out.print(getMinSteps(n)); 
    } 
}

Python3

# Python program for the above program 
import sys 
def getMinSteps(n): 
    
    # If n is equal to 1 
    if (n == 1): 
        return 0; 
  
    sub = sys.maxsize; 
    div2 = sys.maxsize; 
    div3 = sys.maxsize; 
    sub = getMinSteps(n - 1); 
  
    if (n % 2 == 0): 
        div2 = getMinSteps(n // 2); 
  
    if (n % 3 == 0): 
        div3 = getMinSteps(n // 3); 
  
    return 1 + min(sub, min(div2, div3)); 
  
  
# Driver Code 
if __name__ == '__main__': 
    n = 10; 
  
    # Function Call 
    print(getMinSteps(n)); 
  
# This code is contributed by Rajput-Ji  

C#

// C# program for the above program 
using System; 
  
class GFG  
{ 
    public static int getMinSteps(int n) 
    { 
        
        // If n is equal to 1 
        if (n == 1) 
            return 0; 
        
        int sub = Int32.MaxValue; 
        int div2 = Int32.MaxValue; 
        int div3 = Int32.MaxValue; 
        sub = getMinSteps(n - 1); 
        
        if (n % 2 == 0) 
            div2 = getMinSteps(n / 2); 
        
        if (n % 3 == 0) 
            div3 = getMinSteps(n / 3); 
        
        return 1 + Math.Min(sub, Math.Min(div2, div3)); 
    } 
    
    // Driver Code 
    public static void Main(String[] args) 
    { 
        int n = 10; 
        
        // Function Call 
        Console.Write(getMinSteps(n)); 
    } 
} 
  
//This code is contributed by shivansinghss2110

Javascript

<script> 
  
    function getMinSteps(n) 
    { 
        // If n is equal to 1 
        if (n == 1) 
            return 0; 
         
        let sub = Number.MAX_VALUE; 
        let div2 = Number.MAX_VALUE; 
        let div3 = Number.MAX_VALUE; 
        sub = getMinSteps(n - 1); 
         
        if (n % 2 == 0) 
            div2 = getMinSteps(n / 2); 
         
        if (n % 3 == 0) 
            div3 = getMinSteps(n / 3); 
         
        return 1 + Math.min(sub, Math.min(div2, div3)); 
    } 
      
    let n = 10; 
         
    // Function Call 
    document.write(getMinSteps(n)); 
          
</script>

Output

Time Complexity: Exponential(O(2^n))

Auxiliary Space: Exponential(O(2^n)) // because at worst case all 2^n solutions will be stored in the recursive call stack space

This article is contributed by Shivam Pradhan (anuj_charm). If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to contribute@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY