LeetCode 868: Binary Gap

Problem Restatement

We are given a positive integer n.

Write n in binary form.

We need to find the maximum distance between two adjacent 1 bits.

The distance between two bits is the absolute difference between their positions.

Only adjacent 1 bits matter.

Input and Output

Function shape:

class Solution:
    def binaryGap(self, n: int) -> int:
        ...

Examples

Example 1:

n = 22

Binary representation:

10110

The 1 bits appear at positions:

0, 2, 3

Distances:

The maximum is:

2

Example 2:

n = 8

Binary:

1000

There is only one 1 bit, so there are no adjacent pairs.

The answer is:

0

Example 3:

n = 5

Binary:

101

The 1 bits are at positions:

0 and 2

Distance:

2

So the answer is:

2

First Thought: Convert to a Binary String

One simple solution is:

1. Convert n into a binary string.
2. Record the positions of every '1'.
3. Compute distances between consecutive positions.

This works, but we can solve the problem directly with bit operations.

Key Insight

We can scan the bits of n from right to left.

At each step:

1. Check whether the current bit is 1.
2. If yes:
   1. Compare its position with the previous 1 bit.
   2. Update the maximum distance.
3. Shift the number right by one bit.

We only need:

Algorithm

Initialize:

position = 0
last_one = -1
answer = 0

While n > 0:

1. Check the lowest bit:

n & 1

2. If the bit is 1:
   1. If this is not the first 1, compute the distance.
   2. Update the answer.
   3. Store the current position.
3. Shift:

n >>= 1

4. Increase position.

Return answer.

Correctness

The algorithm scans every bit of n exactly once, from least significant to most significant.

Whenever a 1 bit is found, its position is compared with the position of the previous 1 bit. Since bits are processed in order, this previous 1 bit is exactly the adjacent earlier 1.

The difference between the current position and the previous 1 position is therefore the distance between adjacent 1 bits.

The algorithm keeps the maximum of all such distances.

If there are fewer than two 1 bits, no distances are computed, and the answer correctly remains 0.

Therefore, the algorithm returns the maximum distance between adjacent 1 bits.

Complexity

Let:

b = number of bits in n

Since:

b = O(log n)

the runtime is also O(log n).

Implementation

class Solution:
    def binaryGap(self, n: int) -> int:
        position = 0
        last_one = -1
        answer = 0

        while n > 0:
            if n & 1:
                if last_one != -1:
                    answer = max(answer, position - last_one)

                last_one = position

            n >>= 1
            position += 1

        return answer

Code Explanation

We begin with:

position = 0
last_one = -1
answer = 0

position tracks the current bit index.

last_one stores the previous 1 bit position.

The value -1 means no 1 bit has been seen yet.

The loop continues while there are still bits left:

while n > 0:

The expression:

n & 1

checks whether the lowest bit is 1.

If it is:

if n & 1:

and this is not the first 1 bit:

if last_one != -1:

we compute the distance:

position - last_one

and update the maximum:

answer = max(answer, position - last_one)

Then we store the current 1 position:

last_one = position

Next, shift right:

n >>= 1

This removes the lowest bit.

Finally, move to the next bit position:

position += 1

Testing

def test_binary_gap():
    s = Solution()

    assert s.binaryGap(22) == 2
    assert s.binaryGap(5) == 2
    assert s.binaryGap(6) == 1
    assert s.binaryGap(8) == 0
    assert s.binaryGap(1) == 0
    assert s.binaryGap(9) == 3

    print("all tests passed")

test_binary_gap()

Test meaning: