# Binary Gap
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-gap)
Canonical: https://scaleengineer.com/dsa/problems/binary-gap
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [eBay](https://scaleengineer.com/companies/ebay), [X](https://scaleengineer.com/companies/x)
---
## 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.

**Example 1:**

**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.

**Example 2:**

**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.

**Example 3:**

**Input:** n = 5
**Output:** 2
**Explanation:** 5 in binary is "101".

**Constraints:**

* `1 <= n <= 109`

# Approaches
## Convert to String and Store Indices
This approach first converts the integer `n` into its binary string representation. Then, it iterates through this string to find the positions of all the '1's and stores these positions in a list. Finally, it computes the differences between adjacent positions in the list to find the maximum gap.
**Time:** O(log n). The number of bits in `n` is `log n`. Converting to a string, iterating through it, and iterating through the list of indices all take time proportional to `log n`. · **Space:** O(log n). We need space for the binary string (length `log n`) and the list of indices (which can have up to `log n` elements).
**Pros:** Conceptually simple and easy to understand.; Leverages built-in string conversion functions, making the implementation straightforward.
**Cons:** Requires extra space to store the binary string and the list of indices. The space complexity is `O(log n)`, which is less optimal than other approaches.
### Explanation
The core idea is to transform the problem from the domain of integers and bits to the domain of strings and characters, which can be easier to reason about.

First, we use a built-in function like `Integer.toBinaryString(n)` to get the binary representation of `n`.

We then create a list to hold the indices of all '1's. We iterate through the binary string, and whenever we encounter a '1', we add its index to our list.

After populating the list of indices, we check if it contains fewer than two elements. If it does, it means there are no adjacent '1's, so we return 0.

Otherwise, we iterate through the list of indices from the first element to the second-to-last element. In each step, we calculate the distance to the next index (`indices.get(i+1) - indices.get(i)`) and update our maximum distance found so far.

After the loop finishes, the variable holding the maximum distance will contain the answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int binaryGap(int n) {
        String binaryString = Integer.toBinaryString(n);
        List<Integer> oneIndices = new ArrayList<>();
        for (int i = 0; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == '1') {
                oneIndices.add(i);
            }
        }

        if (oneIndices.size() < 2) {
            return 0;
        }

        int maxDistance = 0;
        for (int i = 0; i < oneIndices.size() - 1; i++) {
            int distance = oneIndices.get(i + 1) - oneIndices.get(i);
            if (distance > maxDistance) {
                maxDistance = distance;
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Convert the input integer `n` to its binary string representation.
- Create an empty list, `oneIndices`, to store the indices of '1's.
- Iterate through the binary string. If a character is '1', add its index to `oneIndices`.
- If the size of `oneIndices` is less than 2, return 0.
- Initialize a variable `maxDistance` to 0.
- Iterate through `oneIndices` from the first index up to the second-to-last index.
- In each iteration, calculate the difference between the current index and the next index.
- Update `maxDistance` with this difference if it's larger than the current `maxDistance`.
- Return `maxDistance`.

## One-Pass Iteration on Binary String
This approach improves upon the previous one by avoiding the need to store all indices of '1's. It still converts the number to its binary string representation, but then it finds the maximum gap in a single pass over the string.
**Time:** O(log n). The time is dominated by converting to a string and iterating through it, both of which are proportional to the number of bits. · **Space:** O(log n). Although the auxiliary space for variables is `O(1)`, the space required to store the binary string itself is `O(log n)`.
**Pros:** More space-efficient than storing all indices. The auxiliary space is constant.; Still relatively easy to implement and understand.
**Cons:** Still relies on creating an intermediate string representation, which uses `O(log n)` space.
### Explanation
Similar to the first approach, we begin by converting `n` to its binary string using `Integer.toBinaryString(n)`.

Instead of storing all indices, we only need to remember the index of the most recently seen '1'. We use a variable, say `lastOneIndex`, initialized to a sentinel value like -1.

We iterate through the binary string. When we find a '1', we check if `lastOneIndex` is valid (not -1). If it is, it means we have found an adjacent pair of '1's. We calculate the distance (`currentIndex - lastOneIndex`) and update our `maxDistance`.

Regardless of whether it was the first '1' or not, we update `lastOneIndex` to the current index.

This way, we only need a few variables to keep track of the state, reducing the auxiliary space complexity.

```java
class Solution {
    public int binaryGap(int n) {
        String binaryString = Integer.toBinaryString(n);
        int maxDistance = 0;
        int lastOneIndex = -1;

        for (int i = 0; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == '1') {
                if (lastOneIndex != -1) {
                    int distance = i - lastOneIndex;
                    maxDistance = Math.max(maxDistance, distance);
                }
                lastOneIndex = i;
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Convert the input integer `n` to its binary string representation.
- Initialize `maxDistance = 0` and `lastOneIndex = -1`.
- Iterate through the binary string with index `i`.
- If the character at index `i` is '1':
    a. Check if `lastOneIndex` is not -1.
    b. If it's not, calculate `distance = i - lastOneIndex`.
    c. Update `maxDistance = max(maxDistance, distance)`.
    d. Update `lastOneIndex = i`.
- After the loop, return `maxDistance`.

## Optimal Bit Manipulation
This is the most efficient approach. It avoids any string conversions and works directly with the bitwise representation of the integer. It iterates through the bits of the number, keeping track of the position of the last '1' found and calculating the distance to the current '1'.
**Time:** O(log n). The loop runs for each bit of the number `n`. Since `n` is a 32-bit integer in Java, the loop runs at most 32 times. More generally, it's proportional to the number of bits, which is `log n`. · **Space:** O(1). This approach only uses a few integer variables to store state, regardless of the size of `n`.
**Pros:** Most optimal in terms of space, using only `O(1)` extra space.; Very efficient in terms of time, as it avoids the overhead of string creation and manipulation.
**Cons:** Might be slightly less intuitive for those not comfortable with bitwise operations.
### Explanation
This method processes the number bit by bit, typically from right to left (least significant to most significant).

We use a loop that continues as long as `n` is greater than 0. In each iteration, we examine the rightmost bit and then right-shift the number to process the next bit.

We need variables to track the `maxDistance`, the `currentIndex` (or bit position), and the `lastOneIndex`.

The loop proceeds as follows:
- Check if the rightmost bit is a 1 using the bitwise AND operator (`n & 1`).
- If it is a 1, and we have seen a 1 before (`lastOneIndex != -1`), we calculate the distance `currentIndex - lastOneIndex` and update `maxDistance`. Then, we update `lastOneIndex` to `currentIndex`.
- We then right-shift `n` (`n >>= 1`) to discard the bit we just processed.
- We increment `currentIndex` to move to the next bit position.

This process continues until `n` becomes 0, meaning all bits have been checked. This approach uses only a constant amount of extra space.

```java
class Solution {
    public int binaryGap(int n) {
        int lastOneIndex = -1;
        int maxDistance = 0;
        int currentIndex = 0;
        while (n > 0) {
            if ((n & 1) == 1) { // Check rightmost bit
                if (lastOneIndex != -1) {
                    maxDistance = Math.max(maxDistance, currentIndex - lastOneIndex);
                }
                lastOneIndex = currentIndex;
            }
            n >>= 1; // Right shift to process next bit
            currentIndex++;
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize `maxDistance = 0`, `lastOneIndex = -1` (a sentinel value), and `currentIndex = 0`.
- Loop while `n > 0`.
- Check if the least significant bit of `n` is 1 (i.e., `(n & 1) == 1`).
- If it is 1:
    a. If `lastOneIndex` is not -1, calculate `distance = currentIndex - lastOneIndex`.
    b. Update `maxDistance = max(maxDistance, distance)`.
    c. Update `lastOneIndex = currentIndex`.
- Right-shift `n` by 1 (`n >>= 1`) to process the next bit.
- Increment `currentIndex`.
- After the loop terminates, return `maxDistance`.

# Solutions
### Java

```java
class Solution {
public
  int binaryGap(int n) {
    int ans = 0;
    for (int i = 0, j = -1; n != 0; ++i, n >>= 1) {
      if ((n & 1) == 1) {
        if (j != -1) {
          ans = Math.max(ans, i - j);
        }
        j = i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int binaryGap(int n) {
    int ans = 0;
    for (int i = 0, j = -1; n; ++i, n >>= 1) {
      if (n & 1) {
        if (j != -1)
          ans = max(ans, i - j);
        j = i;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def binaryGap(self, n: int) -> int: ans, j = 0, - 1 for i in range(32): if n & 1: if j != - 1: ans = max(ans, i - j) j = i n >>= 1 return ans

```