> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Binary Gap Python Solution with Tests

> Tested Python solution for LeetCode 868 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 868, [Easy](/catalog/easy). Topics: [Bit Manipulation](/catalog/topics/bit-manipulation). [View on LeetCode](https://leetcode.com/problems/binary-gap/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 868   # by problem number
lcpy gen -s binary_gap   # by problem name
```

## Problem

Given a positive integer `n`, find and return *the **longest distance** between any two **adjacent*** `1`*'s in the binary representation of* `n`. If there are no two adjacent `1`'s, return `0`.

Two `1`'s are **adjacent** if there are only `0`'s separating them (possibly no `0`'s). The **distance** between two `1`'s is the absolute difference between their bit positions. For example, the two `1`'s in `"1001"` have a distance of 3.

### Examples

```
Input: n = 22
Output: 2
```

**Explanation:** 22 in binary is `"10110"`.
The first adjacent pair of 1's is `"10110"` with a distance of 2.
The second adjacent pair of 1's is `"10110"` with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that `"10110"` is not a valid pair since there is a 1 separating the two 1's underlined.

```
Input: n = 8
Output: 0
```

**Explanation:** 8 in binary is `"1000"`.
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

```
Input: n = 5
Output: 2
```

**Explanation:** 5 in binary is `"101"`.

### Constraints

* 1 \<= n \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/binary_gap/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/binary_gap/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(log n)
    # Space: O(1)
    def binary_gap(self, n: int) -> int:
        best = 0
        prev = -1
        i = 0
        while n:
            if n & 1:
                if prev >= 0:
                    best = max(best, i - prev)
                prev = i
            n >>= 1
            i += 1
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(log n) | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.