Binary Gap

Difficulty: Easy | Acceptance: 74.30% | Paid: No Topics: Bit Manipulation

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

Two 1’s are adjacent if there are only 0’s separating them in the binary representation. The distance between two 1’s is the absolute difference in their positions.

• Examples
• Constraints
• Approach 1: String Conversion
• Approach 2: Bit Manipulation

Examples

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is at position 1 and 2 (distance 1).
The second adjacent pair of 1's is at position 2 and 5 (distance 3).
The answer is the maximum of these distances, which is 3.
(Note: The output is 2 based on standard 0-based indexing or correct adjacency logic, but the problem statement text is preserved above).

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints

- 1 <= n <= 10^9

Approach 1: String Conversion

Intuition Convert the integer to its binary string representation and iterate through the characters to find the maximum distance between indices containing ‘1’.

Steps

• Convert the integer n to a binary string.
• Initialize max_dist to 0 and last to -1 to track the index of the last seen ‘1’.
• Iterate through the string with an index i:
  • If the current character is ‘1’:
    • If last is not -1, update max_dist with the maximum of itself and i - last.
    • Update last to the current index i.
• Return max_dist.

class Solution:
    def binaryGap(self, n: int) -> int:
        s = bin(n)[2:]
        max_dist = 0
        last = -1
        for i, char in enumerate(s):
            if char == '1':
                if last != -1:
                    max_dist = max(max_dist, i - last)
                last = i
        return max_dist

Complexity

• Time: O(log n) - The number of bits in n is proportional to log₂(n).
• Space: O(log n) - To store the binary string representation.
• Notes: This approach is intuitive but uses extra space for the string.

Approach 2: Bit Manipulation

Intuition Iterate through the bits of the integer directly using bit shifting and bitwise AND operations to find the maximum distance between set bits without converting to a string.

Steps

• Initialize max_dist to 0, last to -1, and i to 0.
• While n is greater than 0:
  • Check if the least significant bit is 1 using n & 1.
  • If it is 1:
    • If last is not -1, update max_dist with the maximum of itself and i - last.
    • Update last to i.
  • Right shift n by 1 bit (n >>= 1).
  • Increment i.
• Return max_dist.

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

Complexity

• Time: O(log n) - We iterate through each bit of the number once.
• Space: O(1) - We only use a few integer variables for tracking.
• Notes: This is the optimal approach in terms of space complexity.