#868

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Binary Gap

Find the maximum distance between consecutive 1's in a number's binary form using precise bit manipulation techniques.

Problem Statement

Given a positive integer n, determine the longest distance between two consecutive 1's in its binary representation. If n has fewer than two 1's, return 0. The distance between 1's is measured by the number of bits separating them, counting positions from left to right.

For example, n = 22 has a binary representation of "10110". The distances between the consecutive 1's are 2 and 1, so the answer is 2. Your task is to implement a function that computes this maximum distance using a bit manipulation-driven solution strategy.

Examples

Example 1

Input: n = 22

Output: 2

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

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

5 in binary is "101".

Constraints

1 <= n <= 109

Solution Approach

Iterate Through Bits

Use bitwise shifts to traverse each bit of n. Track the index of the last 1 encountered and compute the distance to the current 1. Update the maximum distance whenever a larger gap is found.

Handle Edge Cases

Ensure you return 0 if n contains fewer than two 1's. Avoid counting gaps that start or end outside the actual 1's positions. This prevents incorrect distances when leading or trailing zeros exist.

Optimize with Bit Manipulation

Instead of converting n to a binary string, use n & 1 and n >>= 1 to check bits directly. This reduces memory overhead to O(1) and keeps time complexity O(log N), following the Bit Manipulation-driven solution pattern.

Complexity Analysis

Metric	Value
Time	O(\log N)
Space	O(1)

Time complexity is O(log N) because each bit of n is processed once. Space complexity is O(1) since only a few variables are used to track positions and maximum distance.

What Interviewers Usually Probe

Watch for off-by-one errors when calculating distances between 1's.
Check if the candidate efficiently uses bit operations instead of string conversion.
Listen for clarification questions on how to handle numbers with fewer than two 1's.

Common Pitfalls or Variants

Common pitfalls

Counting the distance incorrectly when multiple zeros separate 1's.
Converting to a string unnecessarily, increasing space complexity.
Failing to update the maximum gap when the last bit is a 1.

Follow-up variants

Find the second-largest binary gap instead of the largest.
Compute the sum of all distances between consecutive 1's.
Return the positions of 1's that form the longest gap.

FAQ

What is a binary gap in this problem?

A binary gap is the distance between two consecutive 1's in the binary representation of n, measured by the number of bits in between.

Can I solve Binary Gap without converting n to a string?

Yes, using bitwise shifts and AND operations allows O(1) space while efficiently iterating through all bits.

What if n has only one 1?

Return 0 because no two 1's exist to form a gap.

Does leading or trailing zeros affect the maximum gap?

No, gaps are only counted between actual 1's, so zeros at the start or end do not inflate the result.

Why is this approach called Bit Manipulation-driven?

Because it processes each bit directly using operators like & and >> without relying on string conversion, following efficient bit manipulation patterns.

terminal

Solution

Solution 1: Bit Manipulation

We use two pointers $\textit{pre}$ and $\textit{cur}$ to represent the positions of the previous and current $1$ bits, respectively. Initially, $\textit{pre} = 100$ and $\textit{cur} = 0$. Then, we traverse the binary representation of $n$. When we encounter a $1$, we calculate the distance between the current position and the previous $1$ position and update the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def binaryGap(self, n: int) -> int:
        ans = 0
        pre, cur = inf, 0
        while n:
            if n & 1:
                ans = max(ans, cur - pre)
                pre = cur
            cur += 1
            n >>= 1
        return ans

Continue Practicing

#864 shortest path to get all keys #861 score after flipping matrix #847 shortest path visiting all nodes