Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The legal bit flips follow reflected Gray-code order: the lower-bit states are traversed forward while the highest bit is zero and backward while it is one. A number containing only bit k therefore needs 2^(k + 1) - 1 moves to reach zero. If lower bits are already set, their position in the reversed traversal subtracts from that distance.

Approach

Let f(0) = 0. For nonzero n, find its highest set-bit index k and clear that bit to obtain the lower-bit remainder. Return 2^(k + 1) - 1 - f(remainder). Each recursive call removes the highest remaining set bit, so the process terminates. The subtraction reflects the traversal's reversed second half; simply adding the independent costs of set bits would ignore the restrictions on higher-bit flips.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0

        # last = 0
        # curr = n
        # while curr:
            # curr //= 2
            # last += 1
        # last -= 1
        # last = 0
        # curr = 1
        # while curr <= n:
            # curr *= 2
            # last += 1
        # last -= 1

        last = n.bit_length() - 1
        return 2 ** (last + 1) - 1 - self.minimumOneBitOperations(n ^ 2**last)

Complexity analysis

Let b = floor(log2(n)) + 1 for n > 0. Time: O(b), because each recursive call clears the current highest set bit. Auxiliary space: O(b) for the recursion stack.