Tutorialspoint.dev

Minimum steps to minimize n as per given condition

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


Output:

3

Below is a tabulation based solution :

C++

// A tabulation based solution in C++
#include <bits/stdc++.h>
using namespace std;
   
int getMinSteps(int n)
{
    int table[n+1];
    for (int i=0; i<=n; i++)
        table[i] = n-i;
    for (int 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 program
int main()
{
    int n = 10;
    cout << getMinSteps(n);
    return 0;
}
// This code is contributed by Jaydeep Rathore

Java

// A tabulation based 
// solution in Java
import java.io.*;
  
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 (String[] args)
{
    int n = 10;
    System.out.print(getMinSteps(n));
}
}
  
// This code is contributed 
// by anuj_67.

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 = 10 
    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.
?>


Output:

3

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter