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 :
- Multiply by 2, i.e., do m = 2 * m
- 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 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 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 + 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 print ( "Minimum number of operations :" , convert(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. ?> |
Javascript
<script> // javascript 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 var m = 3, n = 11; document.write( "Minimum number of " + "operations : " + convert(m, n)); // This code is contributed by Princi Singh </script> |
Output :
Minimum number of operations : 3
References :
http://tech.queryhome.com/112705/convert-number-with-minimum-operations-operations-allowed