Minimum number of steps to reach M from N in Python

In this article, we will learn how to find the minimum number of steps to reach M from N in Python. We are going to use only two operations to reach M from N.

  1. Multiply a number a by 2.
  2. Subtract 1 from number a.

Examples

Input: M = 6, N = 4
Output: 2
Explanation: 
Step 1. Perform operation 2 on N then N become 3.
Step 2. Perform operation 1 on N then N become 6.

Input: M = 4, N=5
Output: 1
Explanation: Perform operation 2 on N.

Minimum number of steps to reach M from N in Python

1. Check if N>M then return the difference between N and M

2. Else if M>N then

  • Check if the M is even then divide M by 2 until it become less than N, if M is odd then add 1 to it add divide it by 2.
  • Each time increase the value of result by 1.

3. Finally, return (result +N-M).

def minSteps(N, M):
    result = 0
    while(M>N):
        if (M&1):
            M += 1
            result += 1

        M //= 2
        result += 1

    return (result + N - M)

N = int(input("Enter the N value: "))
M = int(input("Enter the M value: "))
print("Minimum number of steps to reach M from N is ", minSteps(N, M))

Output

Enter the N value: 5
Enter the M value: 4
Minimum number of steps to reach M from N is 1

Enter the N value: 10
Enter the M value: 15
Minimum number of steps to reach M from N is 4

Also, read

Leave a Reply

Your email address will not be published.