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:
Input : N = 4, M = 6 Output : 2 Explanation : 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 = 1 Output : 9 Explanation : 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
Time Complexity: O(log2m)
Auxiliary Space: O(1)
Contact Us