Minimize steps to reach K from 0 by adding 1 or doubling at each step

0 0 4 minutes read

Given a positive integer K, the task is to find the minimum number of operations of the following two types, required to change 0 to K:

Add one to the operand
Multiply the operand by 2.

Examples:

Input: K = 1
Output: 1
Explanation:
Step 1: 0 + 1 = 1 = K
Input: K = 4
Output: 3
Explanation:
Step 1: 0 + 1 = 1,
Step 2: 1 * 2 = 2,
Step 3: 2 * 2 = 4 = K

Approach:

If K is an odd number, the last step must be adding 1 to it.
If K is an even number, the last step is to multiply by 2 to minimize the number of steps.
Create a dp[] table that stores in every dp[i], the minimum steps required to reach i.

$dp[i] =\begin{cases} dp[i - 1] + 1 & \text{; if i is odd} \\ dp[\frac{i}{2}] + 1 & \text{; if i is even} \end{cases}$

Proof:

Let us consider an even number X
Now we have two options:
i) X-1
ii)X/2
Now if we choose X-1:
-> X-1 is an odd number , since X is even
-> Hence we choose subtract 1 operation and we have X-2
->Now we have X-2, which is also an even number , Now again we have two options either to subtract 1 or to divide by 2
->Now let us choose divide by 2 operation , hence we have ( X – 2 )/2 => (X/2) -1
Now if we choose X/2:
-> We can do the subtract 1 operation to reach (X/2)-1
Now let us consider sequence of both the cases:
When we choose X-1 : X -> X-1 -> X-2 -> (X/2)-1 [ totally three operations ]When we choose X/2 : X -> X/2 -> (X/2)-1 [ totally two operations ]

This diagram shows how choosing divide operation for even numbers leads to optimal solution recursively

Hence we can say that for a given even number , choosing the divide by 2 operation will always give us the minimum number of steps
Hence proved

Below is the implementation of the above approach:

C++

// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
int minOperation(int k)
{
    // vector dp is initialised
    // to store the steps
    vector<int> dp(k + 1, 0);
 
    for (int i = 1; i <= k; i++) {
 
        dp[i] = dp[i - 1] + 1;
 
        // For all even numbers
        if (i % 2 == 0) {
            dp[i]
                = min(dp[i],
                      dp[i / 2] + 1);
        }
    }
    return dp[k];
}
 
// Driver Code
int main()
{
    int K = 12;
    cout << minOperation(k);
}

Java

// Java program to implement the above approach
class GFG{
     
// Function to find minimum operations
static int minOperation(int k)
{
     
    // dp is initialised
    // to store the steps
    int dp[] = new int[k + 1];
 
    for(int i = 1; i <= k; i++)
    {
       dp[i] = dp[i - 1] + 1;
        
       // For all even numbers
       if (i % 2 == 0)
       {
           dp[i] = Math.min(dp[i], dp[i / 2] + 1);
       }
    }
    return dp[k];
}
 
// Driver Code
public static void main (String []args)
{
    int K = 12;
    System.out.print( minOperation(K));
}
}
 
// This code is contributed by chitranayal

Python3

# Python3 program to implement the above approach
 
# Function to find minimum operations
def minOperation(k):
     
    # dp is initialised
    # to store the steps
    dp = [0] * (k + 1)
 
    for i in range(1, k + 1):
        dp[i] = dp[i - 1] + 1
 
        # For all even numbers
        if (i % 2 == 0):
            dp[i]= min(dp[i], dp[i // 2] + 1)
 
    return dp[k]
 
# Driver Code
if __name__ == '__main__':
     
    k = 12
     
    print(minOperation(k))
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement the above approach
using System;
class GFG{
     
// Function to find minimum operations
static int minOperation(int k)
{
     
    // dp is initialised
    // to store the steps
    int []dp = new int[k + 1];
 
    for(int i = 1; i <= k; i++)
    {
        dp[i] = dp[i - 1] + 1;
             
        // For all even numbers
        if (i % 2 == 0)
        {
            dp[i] = Math.Min(dp[i], dp[i / 2] + 1);
        }
    }
    return dp[k];
}
 
// Driver Code
public static void Main()
{
    int K = 12;
    Console.Write(minOperation(K));
}
}
 
// This code is contributed by Nidhi_Biet

Javascript

<script>
// Javascript implementation of the above approach
 
// Function to find minimum operations
function minOperation(k)
{
       
    // dp is initialised
    // to store the steps
    let dp = Array.from({length: k+1}, (_, i) => 0);
   
    for(let i = 1; i <= k; i++)
    {
       dp[i] = dp[i - 1] + 1;
          
       // For all even numbers
       if (i % 2 == 0)
       {
           dp[i] = Math.min(dp[i], dp[i / 2] + 1);
       }
    }
    return dp[k];
}
 
  // Driver Code    
    let K = 12;
    document.write( minOperation(K));
  
 // This code is contributed by target_2.
</script>

Output:

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

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!