# Find the minimum number of steps to reach M from N

Given two integers **N** and **M**. The task is to find the minimum number of steps to reach M from N by performing given operations.

- Multiply a number x by 2. So, x becomes 2*x.
- Subtract one from the number x. So, x becomes x-1.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input :N = 4, M = 6Output :2Explanation :Perform operation number 2 on N. So, N becomes 3 and then perform operation number 1. Then, N becomes 6. So, the minimum number of steps is 2.Input :N = 10, M = 1Output :9Explanation :Perform operation number two 9 times on N. Then N becomes 1.

**Approach **:

The idea is to reverse the problem as follows: We should get the number N starting from M using the operations:

- Divide the number by 2 if it is even.
- Add 1 to the number.

Now, the minimum number of operations would be:

- If N > M, return the difference between them, that is, number of steps will be adding 1 to M until it becomes equal to N.
- Else if N < M.
- Keep dividing M by 2 until it becomes less than N. If M is odd, add 1 to it first and then divide by 2. Once M is less than N, add the difference between them to the count along with the count of above operations.

Below is the implementation of the above approach:

## C++

`// CPP program to find minimum number` `// of steps to reach M from N` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find a minimum number` `// of steps to reach M from N` `int` `Minsteps(` `int` `n, ` `int` `m)` `{` ` ` `int` `ans = 0;` ` ` ` ` `// Continue till m is greater than n` ` ` `while` `(m > n)` ` ` `{` ` ` `// If m is odd` ` ` `if` `(m&1)` ` ` `{` ` ` `// add one` ` ` `m++;` ` ` `ans++;` ` ` `}` ` ` ` ` `// divide m by 2 ` ` ` `m /= 2;` ` ` `ans++;` ` ` `}` ` ` ` ` `// Return the required answer` ` ` `return` `ans + n - m;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 4, m = 6;` ` ` ` ` `cout << Minsteps(n, m);` ` ` ` ` `return` `0;` `}` |

## Java

`// Java program to find minimum number` `// of steps to reach M from N` `class` `CFG` `{` ` ` `// Function to find a minimum number` `// of steps to reach M from N` `static` `int` `Minsteps(` `int` `n, ` `int` `m)` `{` ` ` `int` `ans = ` `0` `;` ` ` ` ` `// Continue till m is greater than n` ` ` `while` `(m > n)` ` ` `{` ` ` `// If m is odd` ` ` `if` `(m % ` `2` `!= ` `0` `)` ` ` `{` ` ` `// add one` ` ` `m++;` ` ` `ans++;` ` ` `}` ` ` ` ` `// divide m by 2 ` ` ` `m /= ` `2` `;` ` ` `ans++;` ` ` `}` ` ` ` ` `// Return the required answer` ` ` `return` `ans + n - m;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `n = ` `4` `, m = ` `6` `;` ` ` ` ` `System.out.println(Minsteps(n, m));` `}` `}` `// This code is contributed by Code_Mech` |

## Python3

`# Python3 program to find minimum number` `# of steps to reach M from N` `# Function to find a minimum number` `# of steps to reach M from N` `def` `Minsteps(n, m):` ` ` `ans ` `=` `0` ` ` ` ` `# Continue till m is greater than n` ` ` `while` `(m > n):` ` ` `# If m is odd` ` ` `if` `(m & ` `1` `):` ` ` ` ` `# add one` ` ` `m ` `+` `=` `1` ` ` `ans ` `+` `=` `1` ` ` ` ` `# divide m by 2 ` ` ` `m ` `/` `/` `=` `2` ` ` `ans ` `+` `=` `1` ` ` ` ` `# Return the required answer` ` ` `return` `ans ` `+` `n ` `-` `m` `# Driver code` `n ` `=` `4` `m ` `=` `6` `print` `(Minsteps(n, m))` `# This code is contributed by mohit kumar` |

## C#

`// C# program to find minimum number` `// of steps to reach M from N` `using` `System;` `class` `GFG` `{` ` ` `// Function to find a minimum number` `// of steps to reach M from N` `static` `int` `Minsteps(` `int` `n, ` `int` `m)` `{` ` ` `int` `ans = 0;` ` ` ` ` `// Continue till m is greater than n` ` ` `while` `(m > n)` ` ` `{` ` ` `// If m is odd` ` ` `if` `(m % 2 != 0)` ` ` `{` ` ` `// add one` ` ` `m++;` ` ` `ans++;` ` ` `}` ` ` ` ` `// divide m by 2 ` ` ` `m /= 2;` ` ` `ans++;` ` ` `}` ` ` ` ` `// Return the required answer` ` ` `return` `ans + n - m;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `n = 4, m = 6;` ` ` ` ` `Console.WriteLine(Minsteps(n, m));` `}` `}` `// This code is contributed` `// by Akanksha Rai` |

## PHP

`<?php` `// PHP program to find minimum number` `// of steps to reach M from N` `// Function to find a minimum number` `// of steps to reach M from N` `function` `Minsteps(` `$n` `, ` `$m` `)` `{` ` ` `$ans` `= 0;` ` ` ` ` `// Continue till m is greater than n` ` ` `while` `(` `$m` `> ` `$n` `)` ` ` `{` ` ` `// If m is odd` ` ` `if` `(` `$m` `% 2 != 0)` ` ` `{` ` ` `// add one` ` ` `$m` `++;` ` ` `$ans` `++;` ` ` `}` ` ` ` ` `// divide m by 2 ` ` ` `$m` `/= 2;` ` ` `$ans` `++;` ` ` `}` ` ` ` ` `// Return the required answer` ` ` `return` `$ans` `+ ` `$n` `- ` `$m` `;` `}` `// Driver code` `$n` `= 4; ` `$m` `= 6;` `echo` `(Minsteps(` `$n` `, ` `$m` `));` `// This code is contributed by Code_Mech` `?>` |

## Javascript

`<script>` `// JavaScript program to find minimum number` `// of steps to reach M from N` `// Function to find a minimum number` `// of steps to reach M from N` `function` `Minsteps(n, m)` `{` ` ` `let ans = 0;` ` ` ` ` `// Continue till m is greater than n` ` ` `while` `(m > n)` ` ` `{` ` ` `// If m is odd` ` ` `if` `(m&1)` ` ` `{` ` ` `// add one` ` ` `m++;` ` ` `ans++;` ` ` `}` ` ` ` ` `// divide m by 2 ` ` ` `m = Math.floor(m / 2);` ` ` `ans++;` ` ` `}` ` ` ` ` `// Return the required answer` ` ` `return` `ans + n - m;` `}` `// Driver code` ` ` `let n = 4, m = 6; ` ` ` `document.write(Minsteps(n, m));` `// This code is contributed by Surbhi Tyagi.` `</script>` |

**Output:**

2