Minimum number of steps to convert one integer to another

Question

Recently i came across a problem, given 2 integers A and B, we need to convert A to B in minimum number of steps. We can perform following operations on A:

• If A is odd, decrease by 1
• If A is even, increase by 1
• Multiply A(even or odd) by 2
• if A is even, divide by 2

again, we have to find the minimum number of steps needed to convert A to B.

The constraints are 0 < A, B < 10^18

My approach: I tried to solve the problem using Breadth First Search, adding all the possible reachable numbers from a step into a queue, but it fails on higher constraints i.e. time outs.

Can anyone suggest a faster alternative?

EDIT: A is not necessarily less than B

Answer 1

The list of available operations is symmetric: 2 sets of operations, each the opposite of the other:

• the last bit can be flipped
• the number can be shifted left one position or right one position if the low bit is 0.

Hence it takes the same number of operations to go from A to B or from B to A.

Going from A to B takes at most the number of operations to go from A to 0 plus the number of operations to go from B to 0. These operations strictly decrease the values of A and B. If along the way an intermediary value can be reached from both A and B, there is no need to go all the way to 0.

Here is a simple function that performs the individual steps on A and B and stops as soon as this common number is found:

def num_ops(a, b):
    # compute the number of ops to transform a into b
    # by symmetry, the same number of ops is needed to transform b into a
    count = 0
    while a != b:
        if a > b:
            if (a & 1) != 0:
                a -= 1
            else:
                a >>= 1
        else:
            if (b & 1) != 0:
                b -= 1
            else:
                b >>= 1
        count += 1
    return count