Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The complement flips only the bits present in the ordinary binary representation, not an unlimited sequence of leading zeros. A result bit is therefore set exactly where an original significant bit was zero.

Approach

Handle zero separately, returning one for the complement of its single digit 0. For a positive input, scan bits from right to left with a position counter. Whenever the lowest bit is zero, add 2^position to the result. Shift the input right and advance the position until no significant bits remain, then return the constructed number.

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

        res = 0
        pos = 0

        while n:
            if (n & 1) == 0:
                res += 2**pos
            n >>= 1
            pos += 1

        return res

Complexity analysis

For b = floor(log₂ n) + 1 bits (with the zero case handled directly), the loop takes O(b) time and O(1) auxiliary space.