# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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

 ` ``\$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
```

## tags:

Mathematical Mathematical