Google FooBar Level 3 - Shortest path to 1
Your intuition is correct. A blind subtraction is the root cause of the problem.

The odd number has the least significant bit equals to 1. An even number has it equal to 0. The more zeroes a number has at the tail, the more divisions you can perform (this is what makes powers of 2 so special - they have all bits but most significant equal to 0). So what you really want is to compute number of trailing 0 bits in n + 1 and n - 1 and pick one which has more:

    tz0 = trailing_zero_bits(n + 1)
    tz1 = trailing_zero_bits(n - 1)
    if tz0 &gt; tz1:
        n = n + 1
    else:
        n = n - 1


Notice how it eliminates computation of closest power of 2.

I leave the implementation of trailing_zero_bits for you. Hint: it is a one-line bit manipulation.