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.
Given a positive integer
N, find and return the longest distance between two consecutive 1’s in the binary representation of
If there aren’t two consecutive 1’s, return 0.
- 1 ≤ N ≤ 2^31
N = 22(Binary:
N = 5(Binary:
N = 6(Binary:
N = 8(Binary:
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.
- Convert the given number,
N, to its binary representation.
- Initialize two pointers:
lastwill track the position of the last 1 we encountered, and
currentwill traverse each bit of the binary representation.
- 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.
- Update the answer if this gap is greater than the previous maximum gap.
- Continue until
currenthas traversed the entire binary representation.
- Return the maximum gap.
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
- Time Complexity: The solution goes through the binary representation of
Nonce, leading to a time complexity of O(log N) because the number of bits in the binary representation of
Nis proportional to log N.
- 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.
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.
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.