How do you solve Binary Gap on LeetCode?

Binary Gap (LeetCode #868) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The binary representation of a number can be analyzed bit by bit.

What is the brute force solution for Binary Gap?

The brute force approach for Binary Gap is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves converting the number to its binary representation and then checking the positions of all '1's to find the maximum gap between them. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Gap?

Binary Gap uses the following concepts: Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Two Pointers.

What are the interview tips for Binary Gap?

Always clarify the problem statement and constraints. Think about edge cases, such as the smallest and largest inputs. Explain your thought process while coding to show your understanding.

What are common mistakes when solving Binary Gap?

Not considering the case where there are no adjacent '1's. Confusing the gap calculation by including '0's between '1's.

#868

Binary Gap

Easy

Bit ManipulationBit ManipulationTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution iterates through the bits of the number while keeping track of the last position of '1' encountered. This allows us to compute the gap in a single pass, improving efficiency.

⚙️

Algorithm

3 steps

1Step 1: Initialize variables to track the last position of '1' and the maximum gap.
2Step 2: Iterate through each bit of the number using bit manipulation.
3Step 3: Whenever a '1' is found, calculate the gap from the last '1' position and update the maximum gap.

solution.py17 lines

1# Full working Python code
2
3def binary_gap(n):
4    last_position = -1
5    max_gap = 0
6    position = 0
7    while n > 0:
8        if n & 1:
9            if last_position != -1:
10                max_gap = max(max_gap, position - last_position)
11            last_position = position
12        n >>= 1
13        position += 1
14    return max_gap
15
16# Example usage
17print(binary_gap(22))  # Output: 2

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the bits of the number. Space complexity is O(1) as we use a constant amount of space.

1The binary representation of a number can be analyzed bit by bit.
2Tracking the last seen position of '1' allows efficient gap calculation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.