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

Ever wondered how computers "see" the distance between data points at the most fundamental level? This problem challenges us to look under the hood of a decimal integer and measure the gaps between its active bits.

---

Problem Summary

You're given:

• A positive integer .

Your goal:

• Find the longest distance between any two adjacent 1s in the binary representation of . If no such pair exists, return 0.

---

Intuition

To solve this, we need to traverse the binary form of the number from right to left. Imagine you are walking along a string of 0s and 1s. Every time you hit a 1, you want to know how many steps you have taken since the last 1 you saw.

The logic follows these steps:

1. We keep track of a distance counter .
2. We initialize with a very small negative value (like -32). This acts as a flag to tell us we haven't found the very first 1 yet.
3. We loop through the bits of using division by 2.
4. If the current bit is 1, we update our maximum distance found so far. We then reset to 0 to start counting for the next gap.
5. If the bit is 0, we simply increment .

By resetting to 0 only when we encounter a 1, we ensure we are measuring the "gap" between the current 1 and the previous one.

---

Walkthrough: Understanding the Examples

*Example 1: *

• Binary of 22 is 10110.
• We see a 1 at the second position (from the right). We mark this as our starting point.
• The next 1 is at the third position. The distance is .
• The next 1 is at the fifth position. The distance between this 1 and the previous one is .
• The largest distance is 2.

*Example 2: *

• Binary of 8 is 1000.
• We find the first 1 at the fourth position.
• We keep looking, but there are no more 1s.
• Since we never found a second 1 to complete a pair, the result is 0.

---

C++ Solution

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 = max(ans, d);
        d = 0;
      }
    }

    return ans;
  }
};

Python Solution

class Solution:
    def binaryGap(self, n: int) -> int:
        ans = 0
        # Initialize distance with a value smaller than any possible bit length
        d = -32

        while n > 0:
            if n % 2 == 1:
                # If we found a 1, update the max distance and reset counter
                if d > ans:
                    ans = d
                d = 0

            n //= 2
            d += 1

        return ans

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var binaryGap = function(n) {
    let ans = 0;
    // d tracks the distance from the last 1 found
    let d = -32;

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

    return ans;
};

---

Key Takeaways

• Bit Manipulation: Understanding how to extract bits using modulo () and right-shifting () is a fundamental skill.
• State Tracking: Using a sentinel value (like -32) to handle the "initial case" prevents the code from counting the distance from the start of the loop to the first 1.
• Efficiency: This solution runs in time, as the number of bits in is proportional to the logarithm of .

---

Final Thoughts

This problem is a fantastic introduction to bitwise logic, which is the heartbeat of low-level systems. In the real world, these concepts are vital for data compression algorithms and network protocols, where every single bit counts and understanding the spacing between data points can optimize storage. In a technical interview, solving this cleanly shows that you can think about how data is structured at the hardware level, not just as abstract numbers.