🌌 Beginner-Friendly Guide 'Binary Gap' - Problem 868 (C++, Python, JavaScript)

Source: Dev.to

Problem Statement

You are given a positive integer n.
Return the longest distance between any two adjacent 1 bits in the binary representation of n.
If there is no such pair, return 0.

Approach

Traverse the binary representation of n from right to left, counting the number of bits since the last seen 1.

1. Keep a distance counter d.
2. Initialize d with a sentinel value (e.g., -32) to indicate that the first 1 has not been encountered yet.
3. While n is greater than 0:
   • If the current least‑significant bit is 1:
     • Update the answer with max(answer, d).
     • Reset d to 0 to start counting the next gap.
   • Otherwise, increment d.
   • Shift n right (or divide by 2) to process the next bit.

Using a sentinel value prevents the first 1 from incorrectly contributing to the maximum distance.

Examples

Example 1

• Input: 22
• Binary: 10110

Result: 2

Example 2

• Input: 8
• Binary: 1000

Only one 1 is present, so no pair exists.

Result: 0

Code

C++

class Solution {
public:
    int binaryGap(int n) {
        int ans = 0;
        // d represents the distance from the last seen 1.
        // Starting at -32 ensures the first 1 found doesn't trigger a max distance update.
        for (int d = -32; n > 0; n /= 2, ++d) {
            if (n % 2 == 1) {
                ans = std::max(ans, d);
                d = 0;
            }
        }
        return ans;
    }
};

Python

class Solution:
    def binaryGap(self, n: int) -> int:
        ans = 0
        d = -32  # sentinel value

        while n > 0:
            if n % 2 == 1:
                ans = max(ans, d)
                d = 0
            n //= 2
            d += 1

        return ans

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var binaryGap = function(n) {
    let ans = 0;
    let d = -32; // sentinel value

    while (n > 0) {
        if (n % 2 === 1) {
            ans = Math.max(ans, d);
            d = 0;
        }
        n = Math.floor(n / 2);
        d++;
    }

    return ans;
};

Key Concepts

• Bit Manipulation: Extract bits using modulo (% 2) and shift/divide by 2.
• State Tracking: A sentinel value (e.g., -32) handles the initial case without extra conditionals.
• Efficiency: The algorithm runs in O(log n) time, proportional to the number of bits in n, and uses O(1) extra space.

Understanding binary gaps is a useful exercise for low‑level problem solving, data compression, and network protocol design, where every bit matters.