# Minimize operations required to obtain N

Given an integer **N**, the task is to obtain **N**, starting from **1** using minimum number of operations. The operations that can be performed in one step are as follows:

- Multiply the number by 2.
- Multiply the number by 3.
- Add 1 to the number.

**Explanation:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 5Output:3Explanation:

Starting value: x = 1

- Multiply x by 2 : x = 2
- Multiply x by 2 : x = 4
- Add 1 to x : x = 5
Therefore, the minimum number of operations required = 3

Input:N = 15Output:4Explanation:

3 operations required to obtain x = 5.

Multiply x by 3 : x = 15.

Therefore, the minimum number of operations required = 4

**Approach:**

The idea is to use the concept of Dynamic Programming. Follow the steps below:

- If minimum operations to obtain any number smaller than
**N**is known, then minimum operations to obtain**N**can be calculated. - Create the following lookup table:

dp[i]= Minimum number of operations to obtain i from 1

- So for any number
**x**, minimum operations required to obtain**x**can be calculated as:

dp[x] = min(dp[x-1], dp[x/2], dp[x/3])

Below is the implementation of the above approach:

## C++

`#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the minimum number` `// of operations` `int` `minOperations(` `int` `n)` `{` ` ` `// Storing the minimum operations` ` ` `// to obtain all numbers up to N` ` ` `int` `dp[n + 1];` ` ` `// Initilal state` ` ` `dp[1] = 0;` ` ` `// Iterate for the remaining numbers` ` ` `for` `(` `int` `i = 2; i <= n; i++) {` ` ` `dp[i] = INT_MAX;` ` ` `// If the number can be obtained` ` ` `// by multiplication by 2` ` ` `if` `(i % 2 == 0) {` ` ` `int` `x = dp[i / 2];` ` ` `if` `(x + 1 < dp[i]) {` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` `// If the number can be obtained` ` ` `// by multiplication by 3` ` ` `if` `(i % 3 == 0) {` ` ` `int` `x = dp[i / 3];` ` ` `if` `(x + 1 < dp[i]) {` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` `// Obtaining the number by adding 1` ` ` `int` `x = dp[i - 1];` ` ` `if` `(x + 1 < dp[i]) {` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` `// Return the minm operations` ` ` `// to obtain n` ` ` `return` `dp[n];` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `n = 15;` ` ` `cout << minOperations(n);` ` ` `return` `0;` `}` |

## Java

`class` `GFG{` ` ` `// Function to find the minimum number` `// of operations` `static` `int` `minOperations(` `int` `n)` `{` ` ` ` ` `// Storing the minimum operations` ` ` `// to obtain all numbers up to N` ` ` `int` `dp[] = ` `new` `int` `[n + ` `1` `];` ` ` `// Initilal state` ` ` `dp[` `1` `] = ` `0` `;` ` ` `// Iterate for the remaining numbers` ` ` `for` `(` `int` `i = ` `2` `; i <= n; i++)` ` ` `{` ` ` `dp[i] = Integer.MAX_VALUE;` ` ` `// If the number can be obtained` ` ` `// by multiplication by 2` ` ` `if` `(i % ` `2` `== ` `0` `)` ` ` `{` ` ` `int` `x = dp[i / ` `2` `];` ` ` `if` `(x + ` `1` `< dp[i])` ` ` `{` ` ` `dp[i] = x + ` `1` `;` ` ` `}` ` ` `}` ` ` ` ` `// If the number can be obtained` ` ` `// by multiplication by 3` ` ` `if` `(i % ` `3` `== ` `0` `)` ` ` `{` ` ` `int` `x = dp[i / ` `3` `];` ` ` `if` `(x + ` `1` `< dp[i])` ` ` `{` ` ` `dp[i] = x + ` `1` `;` ` ` `}` ` ` `}` ` ` `// Obtaining the number by adding 1` ` ` `int` `x = dp[i - ` `1` `];` ` ` `if` `(x + ` `1` `< dp[i])` ` ` `{` ` ` `dp[i] = x + ` `1` `;` ` ` `}` ` ` `}` ` ` `// Return the minm operations` ` ` `// to obtain n` ` ` `return` `dp[n];` `}` `// Driver Code` `public` `static` `void` `main (String []args)` `{` ` ` `int` `n = ` `15` `;` ` ` ` ` `System.out.print( minOperations(n));` `}` `}` `// This code is contributed by chitranayal` |

## Python3

`import` `sys` `# Function to find the minimum number` `# of operations` `def` `minOperations(n):` ` ` ` ` `# Storing the minimum operations` ` ` `# to obtain all numbers up to N` ` ` `dp ` `=` `[sys.maxsize] ` `*` `(n ` `+` `1` `)` ` ` ` ` `# Initial state` ` ` `dp[` `1` `] ` `=` `0` ` ` ` ` `# Iterate for the remaining numbers` ` ` `for` `i ` `in` `range` `(` `2` `, n ` `+` `1` `):` ` ` ` ` `# If the number can be obtained` ` ` `# by multiplication by 2` ` ` `if` `i ` `%` `2` `=` `=` `0` `:` ` ` `x ` `=` `dp[i ` `/` `/` `2` `]` ` ` `if` `x ` `+` `1` `< dp[i]:` ` ` `dp[i] ` `=` `x ` `+` `1` ` ` ` ` `# If the number can be obtained` ` ` `# by multiplication by 3` ` ` `if` `i ` `%` `3` `=` `=` `0` `:` ` ` `x ` `=` `dp[i ` `/` `/` `3` `]` ` ` `if` `x ` `+` `1` `< dp[i]:` ` ` `dp[i] ` `=` `x ` `+` `1` ` ` ` ` `# Obtaining the number by adding 1` ` ` `x ` `=` `dp[i ` `-` `1` `]` ` ` `if` `x ` `+` `1` `< dp[i]:` ` ` `dp[i] ` `=` `x ` `+` `1` ` ` ` ` `# Return the minimum operations` ` ` `# to obtain n` ` ` `return` `dp[n]` `# Driver code` `n ` `=` `15` `print` `(minOperations(n))` ` ` `# This code is contributed by Stuti Pathak` |

## C#

`using` `System;` `class` `GFG{` ` ` `// Function to find the minimum number` `// of operations` `static` `int` `minOperations(` `int` `n)` `{` ` ` ` ` `// Storing the minimum operations` ` ` `// to obtain all numbers up to N` ` ` `int` `[]dp = ` `new` `int` `[n + 1];` ` ` ` ` `int` `x;` ` ` `// Initilal state` ` ` `dp[1] = 0;` ` ` ` ` `// Iterate for the remaining numbers` ` ` `for` `(` `int` `i = 2; i <= n; i++)` ` ` `{` ` ` `dp[i] = ` `int` `.MaxValue;` ` ` ` ` `// If the number can be obtained` ` ` `// by multiplication by 2` ` ` `if` `(i % 2 == 0)` ` ` `{` ` ` `x = dp[i / 2];` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` ` ` `// If the number can be obtained` ` ` `// by multiplication by 3` ` ` `if` `(i % 3 == 0)` ` ` `{` ` ` `x = dp[i / 3];` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` ` ` `// Obtaining the number by adding 1` ` ` `x = dp[i - 1];` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` ` ` `// Return the minm operations` ` ` `// to obtain n` ` ` `return` `dp[n];` `}` ` ` `// Driver Code` `public` `static` `void` `Main (` `string` `[]args)` `{` ` ` `int` `n = 15;` ` ` ` ` `Console.Write(minOperations(n));` `}` `}` ` ` `// This code is contributed by rock_cool` |

## Javascript

`<script>` `// Function to find the minimum number` `// of operations` `function` `minOperations(n)` `{` ` ` ` ` `// Storing the minimum operations` ` ` `// to obtain all numbers up to N` ` ` `let dp = ` `new` `Array(n + 1);` ` ` `// Initilal state` ` ` `dp[1] = 0;` ` ` `// Iterate for the remaining numbers` ` ` `for` `(let i = 2; i <= n; i++)` ` ` `{` ` ` `dp[i] = Number.MAX_VALUE;` ` ` `// If the number can be obtained` ` ` `// by multiplication by 2` ` ` `if` `(i % 2 == 0)` ` ` `{` ` ` `let x = dp[parseInt(i / 2, 10)];` ` ` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` ` ` `// If the number can be obtained` ` ` `// by multiplication by 3` ` ` `if` `(i % 3 == 0)` ` ` `{` ` ` `let x = dp[parseInt(i / 3, 10)];` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` `// Obtaining the number by adding 1` ` ` `let x = dp[i - 1];` ` ` ` ` `if` `(x + 1 < dp[i])` ` ` `{` ` ` `dp[i] = x + 1;` ` ` `}` ` ` `}` ` ` `// Return the minm operations` ` ` `// to obtain n` ` ` `return` `dp[n];` `}` `// Driver code` `let n = 15;` `document.write(minOperations(n));` `// This code is contributed by divyesh072019` `</script>` |

**Output:**

4

**Time Complexity:** O(N) **Auxiliary Space:** O(N)