# 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

| Item | Meaning |
|---|---|
| Input | Positive integer `n` |
| Output | Maximum distance between adjacent `1` bits in binary |
| Adjacent `1`s | Consecutive `1` bits when scanning from left to right |

Function shape:

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

## Examples

Example 1:

```python
n = 22
```

Binary representation:

```python
10110
```

The `1` bits appear at positions:

```python
0, 2, 3
```

Distances:

| Pair | Distance |
|---|---:|
| `0 -> 2` | `2` |
| `2 -> 3` | `1` |

The maximum is:

```python
2
```

Example 2:

```python
n = 8
```

Binary:

```python
1000
```

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

The answer is:

```python
0
```

Example 3:

```python
n = 5
```

Binary:

```python
101
```

The `1` bits are at positions:

```python
0 and 2
```

Distance:

```python
2
```

So the answer is:

```python
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:

| Variable | Purpose |
|---|---|
| `position` | Current bit index |
| `last_one` | Position of previous `1` bit |
| `answer` | Maximum distance found |

## Algorithm

Initialize:

```python
position = 0
last_one = -1
answer = 0
```

While `n > 0`:

1. Check the lowest bit:

```python
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:

```python
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:

```python
b = number of bits in n
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(b)` | We process each bit once |
| Space | `O(1)` | Only a few integer variables are used |

Since:

```python
b = O(log n)
```

the runtime is also `O(log n)`.

## Implementation

```python
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:

```python
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:

```python
while n > 0:
```

The expression:

```python
n & 1
```

checks whether the lowest bit is `1`.

If it is:

```python
if n & 1:
```

and this is not the first `1` bit:

```python
if last_one != -1:
```

we compute the distance:

```python
position - last_one
```

and update the maximum:

```python
answer = max(answer, position - last_one)
```

Then we store the current `1` position:

```python
last_one = position
```

Next, shift right:

```python
n >>= 1
```

This removes the lowest bit.

Finally, move to the next bit position:

```python
position += 1
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `22` → `10110` | Multiple adjacent `1` gaps |
| `5` → `101` | One distance |
| `6` → `110` | Adjacent `1`s next to each other |
| `8` → `1000` | Only one `1` bit |
| `1` → `1` | Smallest positive input |
| `9` → `1001` | Large gap between two `1`s |