Leetcode – Binary Gap Solution in Python

Binary representation of numbers is a fundamental concept in computer science. Often, algorithms or problems involving binary representations challenge a programmer’s ability to understand and manipulate bitwise operations. One such intriguing problem on LeetCode is the Binary Gap problem. This article will delve deep into this problem, providing insights, solutions, and complexity analysis.

Problem Statement

Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.

If there aren’t two consecutive 1’s, return 0.

Constraints:

• 1 ≤ N ≤ 2^31

Examples:

1. Input: N = 22 (Binary: 10110) Output: 2
2. Input: N = 5 (Binary: 101) Output: 2
3. Input: N = 6 (Binary: 110) Output: 1
4. Input: N = 8 (Binary: 1000) Output: 0

Analysis

To solve this problem, we first need to determine the binary representation of the given number. In the binary representation, we are interested in finding the maximum gap (sequence of zeroes) between two 1’s.

One clear insight is that we need to track the position of the last 1 we encountered as we traverse the binary representation. By maintaining this position, whenever we find another 1, we can determine the gap between the two and update our answer if this gap is larger than our previous maximum.

Solution Strategy

1. Convert the given number, N, to its binary representation.
2. Initialize two pointers: last and current. last will track the position of the last 1 we encountered, and current will traverse each bit of the binary representation.
3. As we traverse, if we find a 1, we calculate the gap as current - last - 1. This gives us the number of zeroes between the two 1’s.
4. Update the answer if this gap is greater than the previous maximum gap.
5. Continue until current has traversed the entire binary representation.
6. Return the maximum gap.

Python Code:

def binaryGap(N: int) -> int:
    # Convert the number to its binary representation
    binary_rep = bin(N)[2:]
    
    # Initialize pointers and the answer
    last = None
    ans = 0
    
    # Iterate through the binary representation
    for current in range(len(binary_rep)):
        if binary_rep[current] == '1':
            # If last is not None, calculate the gap
            if last is not None:
                ans = max(ans, current - last)
            # Update the last pointer
            last = current
    
    return ans

Complexity Analysis

1. Time Complexity: The solution goes through the binary representation of N once, leading to a time complexity of O(log N) because the number of bits in the binary representation of N is proportional to log N.
2. Space Complexity: We are using a constant amount of extra space (pointers and variables), leading to a space complexity of O(1).

Alternate Method: Bitwise Operations

Instead of converting the number to its binary string representation, we can manipulate the number directly using bitwise operations.

Python Code:

def binaryGap(N: int) -> int:
    # Track the last position of 1 and the answer
    last = None
    ans = 0
    current = 0
    
    # Iterate while N is not 0
    while N:
        # If the last bit is 1
        if N & 1:
            # If last is not None, calculate the gap
            if last is not None:
                ans = max(ans, current - last)
            # Update the last pointer
            last = current
        # Shift N one bit to the right and move to the next position
        N >>= 1
        current += 1
    
    return ans

This approach directly works on the number N by checking its last bit in each iteration and then right-shifting the number to process the next bit.

Conclusion

The Binary Gap problem is a classic illustration of how understanding binary representation can lead to simple and efficient solutions. While the problem might seem straightforward, it lays the foundation for more complex problems involving bitwise operations and manipulations. As with many algorithmic challenges, understanding the underlying principles and the nature of the data you’re working with can make the path to a solution much clearer. This problem serves as a testament to the beauty of binary operations and their significance in computer science.