Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Adjacent ones mean consecutive set bits when all zero bits are ignored. As we scan bit positions, only the most recent one can form the next such pair. Their position difference already includes the intervening zeros plus the step to the next one.

Approach

Read bits from least to most significant, maintaining a position counter and the last set-bit position.
On a one, compare the distance from the previous one with the maximum, provided a previous one exists. Then update its position.
Shift the number right after each bit and return the maximum. With fewer than two ones, no distance is recorded and the answer stays zero.

class Solution:
    def binaryGap(self, n: int) -> int:
        res = 0
        pos = 0
        last = -1

        while n:
            if n % 2 == 1:
                if last != -1:
                    res = max(res, pos - last)
                last = pos
            n >>= 1
            pos += 1

        return res

Complexity analysis

The loop examines every bit of n, so time is O(log n) and auxiliary space is O(1).