Tutorialspoint.dev

Convert a number m to n using minimum number of given operations

Convert a number m to n with minimum operations. The operations allowed are :

  1. Multiply by 2, i.e., do m = 2 * m
  2. Subtract 1, i.e., do m = m – 1

Print -1 if it is not possible to convert.

Examples :

Input : m = 3, n = 11
Output : 3
1st operation: *2 = 3*2 = 6
2nd operation: *2 = 6*2 = 12
3rd operation: -1 = 12-1 = 11

Input : m = 15, n = 20
Output : 6
1st operation: -1 '5' times = 15 + (-1*5) = 10
2nd operation: *2 = 10*2 = 20

Input : m = 0, n = 8
Output : -1
Using the given set of operations 'm' 
cannot be converted to 'n'

Input : m = 12, n = 8
Output : 4



The idea is based on below facts.
1) If m is less than 0 and n is greater than 0, then not possible.
2) If m is greater than n, then we can reach n using subtractions only.
3) Else (m is less than n), we must do m*2 operations. Following two cases arise.
……a) If n is odd, we must do a -1 operation to reach it.
……b) If n is even, we must do a *2 operation to reach it.

Algorithm:

int convert(m,n)
    if (m == n) 
    return 0;
    
    // not possible
    if (m <= 0 && n > 0)  
    return -1;

    // m is greater than n
    if (m > n) 
        return m-n;

    // n is odd
    if (n % 2 == 1) 
    // perform '-1' 
    return 1 + convert(m, n+1);
        
    // n is even
    else 
    // perform '*2' 
    return 1 + convert(m, n/2);

Note: The list of operations so generated should be applied in reverse order.
For example:

m = 3, n = 11
                convert(3,11)
                     |       --> n is odd:   operation '-1'
                convert(3,12) 
                     |       --> n is even:  operation '*2' 
                convert(3,6)
                     |       --> n is even:  operation '*2' 
                convert(3,3) 
                     |       --> m == n
                   return 
Therefore, the sequence of operations is '*2', '*2', '-1'.

C++

// C++ implementation to convert 
// a number m to n using minimum 
// number of given operations
#include <bits/stdc++.h>
using namespace std;
  
// Function to find minimum 
// number of given operations 
// to convert m to n
int convert(int m, int n)
{
    if (m == n)
        return 0;
  
    // only way is to do
    // -1 (m - n) times
    if (m > n)
        return m - n;
  
    // not possible
    if (m <= 0 && n > 0)
        return -1;
  
    // n is greater and n is odd
    if (n % 2 == 1)
  
        // perform '-1' on m 
        // (or +1 on n)
        return 1 + convert(m, n + 1);
  
    // n is even
    else
        // perform '*2' on m 
        // (or n/2 on n)
        return 1 + convert(m, n / 2);
}
  
// Driver code
int main()
{
    int m = 3, n = 11;
    cout << "Minimum number of operations : "
         << convert(m, n);
    return 0;
}

Java

// Java implementation to convert 
// a number m to n using minimum 
// number of given operations
  
class ConvertNum 
{
    // function to find minimum 
    // number of given operations 
    // to convert m to n
    static int convert(int m, int n)
    {
        if (m == n)
            return 0;
      
        // only way is to do 
        // -1 (m - n) times
        if (m > n)
            return m - n;
      
        // not possible
        if (m <= 0 && n > 0)
            return -1;
      
        // n is greater and n is odd
        if (n % 2 == 1)
      
            // perform '-1' on m 
            // (or +1 on n)
            return 1 + convert(m, n + 1);
      
        // n is even
        else
            // perform '*2' on m 
            // (or n / 2 on n)
            return 1 + convert(m, n / 2);
    }
      
    // Driver Code
    public static void main (String[] args) 
    {
        int m = 3, n = 11;
        System.out.println("Minimum number of "
                                "operations : "
                                  convert(m, n));
    }
}

Python3

# Python implementation to convert
# a number m to n using minimum
# number of given operations
  
# Function to find minimum
# number of given operations
# to convert m to n
def conver(m, n):
  
    if(m == n):
        return 0
  
    # only way is to do
    # -1(m - n): times
    if(m > n):
        return m - n
  
    # not possible
    if(m <= 0 and n > 0):
        return -1
  
    # n is greater and n is odd
    if(n % 2 == 1):
  
        # perform '-1' on m
        #(or +1 on n):
        return 1 + conver(m, n + 1)
  
    # n is even
    else:
          
        # perform '*2' on m
        #(or n/2 on n):
        return 1 + conver(m, n / 2)
  
# Driver code
m = 3
n = 11
print("Minimum number of operations :",
                          conver(m, n))
  
# This code is contributed by
# Sanjit_Prasad

C#

// C# implementation to convert 
// a number m to n using minimum
// number of given operations
using System;
  
class GFG
{
    // function to find minimum 
    // number of given operations
    // to convert m to n
    static int convert(int m, int n)
    {
        if (m == n)
            return 0;
      
        // only way is to do 
        // -1 (m - n) times
        if (m > n)
            return m - n;
      
        // not possible
        if (m <= 0 && n > 0)
            return -1;
      
        // n is greater and n is odd
        if (n % 2 == 1)
      
            // perform '-1' on m 
            // (or +1 on n)
            return 1 + convert(m, n + 1);
      
        // n is even
        else
            // perform '*2' on m 
            // (or n / 2 on n)
            return 1 + convert(m, n / 2);
    }
      
    // Driver code
    public static void Main () 
    {
        int m = 3, n = 11;
        Console.Write("Minimum number of "
                           "operations : "
                             convert(m, n));
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// PHP implementation to convert 
// a number m to n using minimum 
// number of given operations
  
// Function to find minimum
// number of given operations
// to convert m to n
function convert($m, $n)
{
    if ($m == $n)
        return 0;
  
    // only way is to do 
    // -1 (m - n) times
    if ($m > $n)
        return $m - $n;
  
    // not possible
    if ($m <= 0 && $n > 0)
        return -1;
  
    // n is greater and n is odd
    if ($n % 2 == 1)
  
        // perform '-1' on m 
        // (or +1 on n)
        return 1 + convert($m, $n + 1);
  
    // n is even
    else
        // perform '*2' on m 
        // (or n/2 on n)
        return 1 + convert($m, $n / 2);
}
  
// Driver code
{
    $m = 3; $n = 11;
    echo "Minimum number of "
              "operations : "
              convert($m, $n);
    return 0;
}     
  
// This code is contributed
// by nitin mittal.
?>


Output :

Minimum number of operations : 3

References :
http://tech.queryhome.com/112705/convert-number-with-minimum-operations-operations-allowed

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter