Domain 1EasyCORE

Binary Gap

The problem requires finding the longest distance between any two adjacent `1`s 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 `1`s. If there are no adjacent `1`s, the function should return `0`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

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 of n.

Implicit Constraints or Edge Cases:

  • The input is always a positive integer.
  • If there are no two adjacent 1s, return 0.
  • Consider edge cases like n = 1 (binary “1”) and n = 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

  1. Initialize variables:

    • max_distance to store the maximum distance found.
    • last_position to keep track of the position of the last seen 1.
    • A counter position starting from 0 to track the current bit position.
  2. Traverse the bits of n from 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 seen 1 and update max_distance if this distance is greater.
    • Update last_position to the current position.
    • Right shift n by 1 to process the next bit.
  3. 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 returns 0.
  • n = 8: The binary representation is “1000”. There are no adjacent 1s, so the function returns 0.
  • n = 22: The binary representation is “10110”. The maximum distance between adjacent 1s is 2, which the function correctly identifies.
  • n = 5: The binary representation is “101”. The maximum distance between adjacent 1s is 2, which the function correctly identifies.
  • n = 6: The binary representation is “110”. The maximum distance between adjacent 1s is 1, which the function correctly identifies.

The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem statement.