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.
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++
#include <bits/stdc++.h>
using namespace std;
int getMinSteps( int n, int *memo)
{
if (n == 1)
return 0;
if (memo[n] != -1)
return memo[n];
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));
memo[n] = 1 + res;
return memo[n];
}
int getMinSteps( int n)
{
int memo[n+1];
for ( int i=0; i<=n; i++)
memo[i] = -1;
return getMinSteps(n, memo);
}
int main()
{
int n = 10;
cout << getMinSteps(n);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int getMinSteps( int n, int memo[])
{
if (n == 1 )
return 0 ;
if (memo[n] != - 1 )
return memo[n];
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));
memo[n] = 1 + res;
return memo[n];
}
static int getMinSteps( int n)
{
int memo[] = new int [n + 1 ];
for ( int i = 0 ; i <= n; i++)
memo[i] = - 1 ;
return getMinSteps(n, memo);
}
public static void main (String[] args)
{
int n = 10 ;
System.out.println(getMinSteps(n));
}
}
|
Python3
def getMinSteps(n, memo):
if (n = = 1 ):
return 0
if (memo[n] ! = - 1 ):
return memo[n]
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))
memo[n] = 1 + res
return memo[n]
def getsMinSteps(n):
memo = [ 0 for i in range (n + 1 )]
for i in range (n + 1 ):
memo[i] = - 1
return getMinSteps(n, memo)
n = 10
print (getsMinSteps(n))
|
C#
using System;
class GFG {
static int getMinSteps( int n, int []memo)
{
if (n == 1)
return 0;
if (memo[n] != -1)
return memo[n];
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));
memo[n] = 1 + res;
return memo[n];
}
static int getMinSteps( int n)
{
int []memo = new int [n + 1];
for ( int i = 0; i <= n; i++)
memo[i] = -1;
return getMinSteps(n, memo);
}
public static void Main ()
{
int n = 10;
Console.WriteLine(getMinSteps(n));
}
}
|
PHP
<?php
function getMinSteps( $n , $memo )
{
if ( $n == 1)
return 0;
if ( $memo [ $n ] != -1)
return $memo [ $n ];
$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 ));
$memo [ $n ] = 1 + $res ;
return $memo [ $n ];
}
function g_etMinSteps( $n )
{
$memo = array ();
for ( $i = 0; $i <= $n ; $i ++)
$memo [ $i ] = -1;
return getMinSteps( $n , $memo );
}
$n = 10;
echo g_etMinSteps( $n );
?>
|
Javascript
<script>
function getMinSteps(n , memo)
{
if (n == 1)
return 0;
if (memo[n] != -1)
return memo[n];
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));
memo[n] = 1 + res;
return memo[n];
}
function getMinStep(n) {
var memo = Array(n + 1).fill(0);
for ( var i = 0; i <= n; i++)
memo[i] = -1;
return getMinSteps(n, memo);
}
var n = 10;
document.write(getMinStep(n));
</script>
|
Time Complexity: O(n), as there will be n unique calls.
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];
}
int main()
{
int n = 14;
cout << getMinSteps(n);
return 0;
}
|
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];
}
public static void main(String[] args)
{
int n = 14 ;
System.out.print(getMinSteps(n));
}
}
|
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 ]
if __name__ = = "__main__" :
n = 14
print (getMinSteps(n))
|
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];
}
public static void Main ()
{
int n = 10;
Console.WriteLine(getMinSteps(n));
}
}
|
PHP
<?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];
}
$n = 10;
echo getMinSteps( $n );
?>
|
Javascript
<script>
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>
|
Time Complexity: O(n), as there will be n unique calls.
C++
#include <bits/stdc++.h>
using namespace std;
int getMinSteps( int n)
{
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));
}
int main()
{
int n = 10;
cout << (getMinSteps(n));
}
|
Java
import java.io.*;
class GFG {
public static int getMinSteps( int n)
{
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));
}
public static void main(String[] args)
{
int n = 10 ;
System.out.print(getMinSteps(n));
}
}
|
Python3
import sys
def getMinSteps(n):
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));
if __name__ = = '__main__' :
n = 10 ;
print (getMinSteps(n));
|
C#
using System;
class GFG
{
public static int getMinSteps( int n)
{
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));
}
public static void Main(String[] args)
{
int n = 10;
Console.Write(getMinSteps(n));
}
}
|
Javascript
<script>
function getMinSteps(n)
{
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;
document.write(getMinSteps(n));
</script>
|
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