Code Implementation

class Solution:
    def binaryGap(self, n: int) -> int:
        last = -1
        max_gap = 0
        i = 0
        while n > 0:
            if n & 1:
                if last != -1:
                    max_gap = max(max_gap, i - last)
                last = i
            n >>= 1
            i += 1
        return max_gap
      

class Solution {
public:
    int binaryGap(int n) {
        int last = -1, max_gap = 0, i = 0;
        while (n > 0) {
            if (n & 1) {
                if (last != -1) {
                    max_gap = std::max(max_gap, i - last);
                }
                last = i;
            }
            n >>= 1;
            ++i;
        }
        return max_gap;
    }
};
      

class Solution {
    public int binaryGap(int n) {
        int last = -1, maxGap = 0, i = 0;
        while (n > 0) {
            if ((n & 1) != 0) {
                if (last != -1) {
                    maxGap = Math.max(maxGap, i - last);
                }
                last = i;
            }
            n >>= 1;
            i++;
        }
        return maxGap;
    }
}
      

var binaryGap = function(n) {
    let last = -1, maxGap = 0, i = 0;
    while (n > 0) {
        if ((n & 1) === 1) {
            if (last !== -1) {
                maxGap = Math.max(maxGap, i - last);
            }
            last = i;
        }
        n >>= 1;
        i++;
    }
    return maxGap;
};
      

Problem Description

Given a positive integer n, find and return the longest distance between two consecutive 1's in the binary representation of n. If there are no two consecutive 1's, return 0.

The "distance" is defined as the number of positions between two 1's in the binary string (counted from the least significant bit, starting at index 0). Only consider gaps between 1's; ignore 0's at the start or end that are not between two 1's.

Constraints:

• 1 <= n <= 10^9
• There is exactly one input integer n.

Thought Process

The problem asks for the largest gap between two 1's in the binary representation of a number. The naive approach might be to convert the number to a binary string, look for all pairs of 1's, and compute the distances between them.

However, directly processing the bits of the number without converting to a string is more efficient. We can scan the bits from least significant to most significant, record the positions of 1's, and compute the gaps as we go.

The key insight is to track the index of the last seen 1 bit, and whenever we find a new 1 bit, compute the distance from the last 1, updating the maximum gap found so far.

Solution Approach

• Step 1: Initialize two variables: one (last) to keep track of the index of the last seen 1 bit (start with -1), and another (max_gap) to keep track of the largest gap found.
• Step 2: Start scanning the bits of n from the least significant bit (rightmost) to the most significant bit (leftmost) using bitwise operations.
• Step 3: For each bit, if the bit is 1:
  • If last is not -1, compute the gap between the current bit index and last and update max_gap if this gap is larger.
  • Update last to the current bit index.
• Step 4: Shift n right by 1 to process the next bit, and increment the bit index.
• Step 5: Continue until all bits are processed. Return max_gap at the end.

This approach is efficient because it only examines each bit once and uses constant extra space.

Example Walkthrough

Let's use n = 22 as an example. The binary representation of 22 is 10110.

• Starting from the right (least significant bit):
  • Bit 0: 0 (skip)
  • Bit 1: 1 (first 1 found at index 1, set last = 1)
  • Bit 2: 1 (second 1 found at index 2, gap is 2 - 1 = 1, max_gap = 1, update last = 2)
  • Bit 3: 0 (skip)
  • Bit 4: 1 (third 1 found at index 4, gap is 4 - 2 = 2, max_gap = 2, update last = 4)
• No more bits. The maximum gap found is 2.

So, binaryGap(22) returns 2.

Time and Space Complexity

• Brute-force Approach: Convert n to a binary string, find all indices of 1's, and compute all pairwise distances. This takes O(k) time for conversion and O(k) space for storing indices, where k is the number of bits.
• Optimized Approach: The presented method scans each bit of n once, so the time complexity is O(log n), since that's the number of bits in n. The space complexity is O(1), as only a few integer variables are used.

Summary

To solve the Binary Gap problem, we efficiently scan each bit of the input number, keeping track of the positions of 1's and updating the maximum gap found. This approach avoids unnecessary conversions or extra storage, leveraging bitwise operations for both speed and simplicity. The result is a clean, fast, and elegant solution that works for all valid inputs.