Minimize operations required to obtain N

Namachila October 13, 2025

0 0 5 minutes read

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:

Input: N = 5
Output: 3
Explanation:
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 = 15
Output: 4
Explanation:
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];
 
    // Initial 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];
 
    // Initial 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;
    // Initial 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);
 
    // Initial 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:

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

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 zambiatek!