868. Binary Gap
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 61.0%
Problem Breakdown
The problem requires finding the longest distance between any two adjacent 1s in the binary representation of a given positive integer n. The input is a single integer n where 1 <= n <= 10^9. The output should be an integer representing the maximum distance between two adjacent 1s. If there are no adjacent 1s, the function should return 0.
Inputs:
- A positive integer
n
Outputs:
- An integer representing the longest distance between any two adjacent
1s in the binary representation ofn.
Implicit Constraints or Edge Cases:
- The input is always a positive integer.
- If there are no two adjacent
1s, return0. - Consider edge cases like
n = 1(binary “1”) andn = 8(binary “1000”).
Intuition
A brute-force approach would involve converting the number to its binary representation, iterating through each bit, and checking distances between every pair of 1s. This approach is inefficient because it involves multiple passes over the bits.
The key insight is to traverse the bits from right to left, keeping track of the position of the last seen 1. By doing this, we can compute the distance between consecutive 1s in a single pass, which significantly reduces both time and space complexity.
Approach
-
Initialize variables:
max_distanceto store the maximum distance found.last_positionto keep track of the position of the last seen1.- A counter
positionstarting from 0 to track the current bit position.
-
Traverse the bits of
nfrom right to left using bitwise operations:- Use a loop to process each bit until all bits are processed.
- In each iteration, check if the least significant bit (LSB) is
1. - If it is
1, calculate the distance from the last seen1and updatemax_distanceif this distance is greater. - Update
last_positionto the current position. - Right shift
nby 1 to process the next bit.
-
Return
max_distance.
Complexity Analysis
- Time Complexity: O(log n) because we are processing each bit of the integer, and there are log₂(n) bits in an integer
n. - Space Complexity: O(1) as we are using a constant amount of extra space regardless of the input size.
Solution
def binary_gap(n: int) -> int:
max_distance = 0
last_position = -1
position = 0
while n > 0:
if n & 1: # Check if the least significant bit is 1
if last_position != -1:
max_distance = max(max_distance, position - last_position)
last_position = position
n >>= 1 # Right shift n to process the next bit
position += 1
return max_distance
Edge Cases Handled
- n = 1: The binary representation is “1”. There are no adjacent
1s, so the function returns0. - n = 8: The binary representation is “1000”. There are no adjacent
1s, so the function returns0. - n = 22: The binary representation is “10110”. The maximum distance between adjacent
1s is2, which the function correctly identifies. - n = 5: The binary representation is “101”. The maximum distance between adjacent
1s is2, which the function correctly identifies. - n = 6: The binary representation is “110”. The maximum distance between adjacent
1s is1, which the function correctly identifies.
The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem statement.