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

div class="responsive-tabs">

## C++

 `// CPP program to minimize n to 1 by given ` `// rule in minimum steps ` `#include ` `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

 ` `

Output:

```3
```

Below is a tabulation based solution :

## C++

 `// A tabulation based solution in C++ ` `#include ` `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

 `= 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
```

## tags:

Dynamic Programming Dynamic Programming