Binary Gap

Binary Gap

What is this problem about?

The "Binary Gap interview question" is a bit manipulation challenge. Given a positive integer $n$, you need to find its binary representation and identify the largest distance between any two adjacent 1s. For example, if $n=22$, its binary form is 10110. The distance between the first '1' and second '1' is 2, and the distance between the second '1' and third '1' is 1. The maximum "binary gap" here is 2.

Why is this asked in interviews?

Companies like Twitter and Amazon ask the "Binary Gap coding problem" to evaluate a candidate's proficiency with Bit Manipulation. It tests whether a candidate can process the bits of a number without explicitly converting it into a string. It’s a core test of "Math interview pattern" and iterative logic.

Algorithmic pattern used

This problem follows the Bit Shifting and Tracking pattern.

1. Initialize: Set max_gap = 0 and last_position = -1.
2. Iterate through bits: Use a loop to check each bit of the number (usually up to 31 bits for a standard integer).
3. Check bit: Use (n >> i) & 1 to check if the $i^{th}$ bit is 1.
4. Calculate Gap:
   • If the bit is 1 and last_position is not -1, calculate the distance: i - last_position.
   • Update max_gap if this distance is larger.
   • Set last_position = i.
5. Shift: Continue until all bits are processed.

Example explanation

$n = 13$ (Binary: 1101)

• Bit 0: Value is 1. last_position = 0.
• Bit 1: Value is 0.
• Bit 2: Value is 1. Gap = $2 - 0 = 2$. max_gap = 2, last_position = 2.
• Bit 3: Value is 1. Gap = $3 - 2 = 1$. max_gap = 2, last_position = 3. Result: 2.

Common mistakes candidates make

• Ignoring single '1's: If a number has only one '1' (like 8, which is 1000), the answer should be 0, but some algorithms might return the position of the 1 instead.
• String conversion: Converting the number to a binary string and then iterating. While this works, it uses extra memory and is often seen as less "idiomatic" than direct bit manipulation.
• Wrong distance calculation: Being off-by-one when calculating the distance between indices.

Interview preparation tip

Practice using the bitwise operators >>, &, and |. Being able to extract bits from an integer is a vital skill for "Bit Manipulation interview pattern" problems.