LeetCode 868 - Binary Gap

The problem asks us to examine the binary representation of a positive integer n and determine the largest distance between two adjacent 1 bits. A binary number is made up of 0s and 1s.

leetcodeeasybit-manipulation

LeetCode Problem 868

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to examine the binary representation of a positive integer n and determine the largest distance between two adjacent 1 bits.

A binary number is made up of 0s and 1s. For example:

  • 22 in binary is 10110
  • 5 in binary is 101
  • 8 in binary is 1000

We are interested only in positions where the bit is 1. Among those 1s, we look at pairs that are adjacent in the sense that there are no other 1s between them.

For example, in 10110:

  • The first and second 1 bits are separated by one 0, so their distance is 2
  • The second and third 1 bits are next to each other, so their distance is 1

The answer is the maximum of these distances.

The input is a single integer n, where:

  • 1 <= n <= 10^9

Since 10^9 fits comfortably within 32 bits, the binary representation is very small. This immediately suggests that even scanning every bit one by one will be extremely efficient.

There are several important edge cases:

  • Numbers with only one 1 bit, such as 8 (1000), should return 0
  • Numbers with consecutive 1s, such as 3 (11), should return 1
  • Numbers with large gaps between 1s, such as 17 (10001), should correctly compute the larger distance
  • The smallest valid input, 1, contains only a single 1, so the answer is 0

The problem guarantees that n is positive, so we never need to handle negative values or an empty binary representation.

Approaches

Brute Force Approach

A straightforward approach is to first convert the number into a binary string using a built-in conversion function.

For example:

22 -> "10110"

We can then scan the string from left to right and record the positions of every 1. Whenever we encounter a new 1, we calculate the distance from the previous 1 and update the maximum distance.

This approach is correct because every pair of adjacent 1s is examined exactly once.

Although this solution is already fast enough for the given constraints, it uses extra space for the binary string conversion.

Optimal Approach

A more efficient and elegant solution uses direct bit manipulation.

Instead of converting the number into a string, we process the bits one at a time using bitwise operations:

  • n & 1 checks whether the current bit is 1
  • n >>= 1 shifts the bits to the right

While scanning the bits, we track:

  • The current bit position
  • The position of the previous 1
  • The maximum gap found so far

Whenever we encounter a new 1, we compute the distance from the previous 1.

This works well because binary representation is inherently bit-based, so bit manipulation lets us process the number directly without extra memory allocation.

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(log n) Converts integer to binary string and scans it
Optimal O(log n) O(1) Processes bits directly using bit manipulation

Algorithm Walkthrough

  1. Initialize a variable max_gap to 0. This will store the largest distance found between adjacent 1s.

  2. Initialize a variable previous_one_position to -1. This variable remembers the position of the last 1 bit we encountered. A value of -1 means we have not seen any 1 yet.

  3. Initialize a variable position to 0. This represents the current bit position while scanning from right to left.

  4. While n is greater than 0, continue processing bits one at a time.

  5. Check whether the current bit is 1 using n & 1.

  6. If the current bit is 1:

  7. If previous_one_position is not -1, compute the distance:

position - previous_one_position
  1. Update max_gap if this distance is larger.
  2. Store the current position as the new previous_one_position.
  3. Shift the number right by one bit using:
n >>= 1

This moves the next bit into the least significant position. 8. Increment position by 1. 9. After all bits have been processed, return max_gap.

Why it works

The algorithm scans every bit exactly once in order from least significant to most significant. Every time a 1 bit is encountered, the algorithm compares its position with the previous 1 bit position. Since adjacent 1s are encountered consecutively during the scan, every valid gap is measured exactly once. Taking the maximum of these distances guarantees the correct answer.

Python Solution

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

        while n > 0:
            if n & 1:
                if previous_one_position != -1:
                    gap = position - previous_one_position
                    max_gap = max(max_gap, gap)

                previous_one_position = position

            n >>= 1
            position += 1

        return max_gap

The implementation closely follows the algorithm described earlier.

The variable max_gap stores the best answer found so far. The variable previous_one_position tracks the location of the last 1 bit. The variable position keeps track of the current bit index.

The expression n & 1 checks whether the least significant bit is 1. If it is, we compute the distance from the previous 1 and update the answer if necessary.

The operation n >>= 1 shifts the bits to the right, allowing us to process the next bit during the next iteration.

Because we never store the binary representation explicitly, the solution uses constant extra space.

Go Solution

func binaryGap(n int) int {
    maxGap := 0
    previousOnePosition := -1
    position := 0

    for n > 0 {
        if n&1 == 1 {
            if previousOnePosition != -1 {
                gap := position - previousOnePosition

                if gap > maxGap {
                    maxGap = gap
                }
            }

            previousOnePosition = position
        }

        n >>= 1
        position++
    }

    return maxGap
}

The Go implementation mirrors the Python logic almost exactly.

One small difference is that Go does not provide Python's built-in max() function for integers, so we use a standard if statement to update maxGap.

Since the constraints are small, integer overflow is not a concern. The solution also uses constant extra space in Go.

Worked Examples

Example 1

Input:

n = 22

Binary representation:

10110

Processing occurs from right to left because we examine the least significant bit first.

Iteration Current Bit Position Previous 1 Position Gap Max Gap
1 0 0 -1 - 0
2 1 1 -1 - 0
3 1 2 1 1 1
4 0 3 2 - 1
5 1 4 2 2 2

Final answer:

2

Example 2

Input:

n = 8

Binary representation:

1000
Iteration Current Bit Position Previous 1 Position Gap Max Gap
1 0 0 -1 - 0
2 0 1 -1 - 0
3 0 2 -1 - 0
4 1 3 -1 - 0

There is only one 1, so no valid pair exists.

Final answer:

0

Example 3

Input:

n = 5

Binary representation:

101
Iteration Current Bit Position Previous 1 Position Gap Max Gap
1 1 0 -1 - 0
2 0 1 0 - 0
3 1 2 0 2 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(log n) We process each bit of the number once
Space O(1) Only a few variables are used

The number of iterations equals the number of bits in n. Since a number with value n contains approximately log2(n) bits, the running time is O(log n).

The algorithm does not allocate any extra data structures proportional to the input size, so the auxiliary space complexity is constant.

Test Cases

solution = Solution()

assert solution.binaryGap(22) == 2  # Example case: 10110
assert solution.binaryGap(8) == 0   # Only one 1 bit
assert solution.binaryGap(5) == 2   # 101

assert solution.binaryGap(1) == 0   # Smallest valid input
assert solution.binaryGap(2) == 0   # 10, only one 1
assert solution.binaryGap(3) == 1   # 11, adjacent bits

assert solution.binaryGap(9) == 3   # 1001
assert solution.binaryGap(17) == 4  # 10001
assert solution.binaryGap(20) == 2  # 10100

assert solution.binaryGap(6) == 1   # 110
assert solution.binaryGap(10) == 2  # 1010
assert solution.binaryGap(42) == 2  # 101010

assert solution.binaryGap(1041) == 5  # 10000010001
Test Why
22 -> 2 Validates multiple adjacent gaps
8 -> 0 Validates single 1 case
5 -> 2 Validates separated 1s
1 -> 0 Smallest valid input
2 -> 0 Binary with one 1 and trailing zeros
3 -> 1 Consecutive 1s
9 -> 3 Larger gap between two 1s
17 -> 4 Very large gap
20 -> 2 Internal zero spacing
6 -> 1 Consecutive high bits
10 -> 2 Alternating bit pattern
42 -> 2 Multiple equal gaps
1041 -> 5 Larger binary representation stress case

Edge Cases

One important edge case is when the number contains only a single 1 bit. Examples include 1, 2, 4, and 8. In these cases, no adjacent pair of 1s exists, so the answer must be 0. A buggy implementation might accidentally return an uninitialized value or compute an invalid distance. This implementation avoids that problem by initializing previous_one_position to -1 and only computing a gap after a previous 1 has already been seen.

Another important edge case is when the binary representation contains consecutive 1s, such as 3 (11) or 6 (110). The distance between consecutive bit positions is 1, which is the minimum valid gap. Some incorrect implementations mistakenly count the number of zeros between 1s instead of the distance between positions. This implementation correctly computes the positional difference, so consecutive 1s produce a gap of 1.

A third important edge case is when the maximum gap appears near the most significant bits, such as 17 (10001). An incorrect implementation might terminate too early or fail to track the correct bit position during shifts. This solution increments the position variable on every iteration, ensuring that all bit distances are measured accurately regardless of where the 1s appear in the number.