Problem Description

Given a positive integer n, you need to find the longest distance between any two adjacent 1s in its binary representation. If there are no two adjacent 1s in the binary representation, return 0.

Two 1s are considered adjacent if they appear consecutively in the binary representation with only 0s (or no 0s) between them. The distance between two 1s is calculated as the absolute difference between their bit positions.

For example:

• In the binary string "1001", there are two 1s at positions 0 and 3 (counting from the right, starting at 0)
• These two 1s are adjacent because there are no other 1s between them
• The distance between them is 3 - 0 = 3

The task is to examine all pairs of adjacent 1s in the binary representation and return the maximum distance found. If the binary representation has fewer than two 1s, there are no adjacent pairs, so the answer would be 0.

Intuition

To find the longest distance between adjacent 1s, we need to track where each 1 appears in the binary representation. The key insight is that we don't need to store all positions of 1s - we only need to remember the position of the previous 1 to calculate distances.

Think of it like walking along the binary digits from right to left. Every time we encounter a 1, we can calculate how far we've walked since the last 1 we saw. This distance is simply the difference between the current position and the previous position where we found a 1.

We can process the number bit by bit using bit manipulation. By checking the least significant bit with n & 1, we can determine if the current position has a 1. After checking each bit, we shift the number right with n >>= 1 to examine the next bit.

The algorithm maintains:

• pre: the position of the previous 1 we encountered (initialized to infinity to handle the first 1 gracefully)
• cur: our current position in the binary representation
• ans: the maximum distance found so far

Each time we find a 1, we calculate cur - pre to get the distance from the previous 1, update our answer if this distance is larger, and then update pre to the current position. This way, we're always comparing adjacent 1s and keeping track of the maximum gap between them.

Solution Approach

The solution uses bit manipulation to efficiently traverse the binary representation of n from right to left (least significant bit to most significant bit).

Variables Used:

• ans: Stores the maximum distance found between adjacent 1s
• pre: Position of the previous 1 bit (initialized to infinity)
• cur: Current bit position being examined (starts at 0)

Algorithm Steps:

1. Initialize variables: Set ans = 0, pre = inf, and cur = 0. The pre = inf initialization ensures that when we find the first 1, the distance calculation cur - pre will be negative, which won't affect our answer since we're looking for the maximum.

2. Traverse bits: Use a while loop that continues as long as n > 0:

   • Check if the current bit is 1 using n & 1
   • If it's a 1:
     • Calculate the distance from the previous 1: cur - pre
     • Update the maximum distance: ans = max(ans, cur - pre)
     • Update pre to the current position: pre = cur
   • Increment the position counter: cur += 1
   • Shift n right by one bit: n >>= 1

3. Return result: After processing all bits, return ans

Why this works:

• By checking n & 1, we examine the least significant bit
• Right-shifting with n >>= 1 moves to the next bit
• We only update pre when we find a 1, ensuring we're always measuring distances between consecutive 1s
• The max() function ensures we keep track of the longest distance encountered

Time Complexity: O(log n) where n is the input number, as we process each bit once. Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with n = 22, which has binary representation 10110.

Initial State:

• ans = 0 (maximum distance found)
• pre = inf (position of previous 1)
• cur = 0 (current position)
• n = 22 (binary: 10110)

Step-by-step execution:

Iteration 1: Binary: 10110, checking rightmost bit

• n & 1 = 0 (rightmost bit is 0)
• No action since bit is 0
• cur = 1, n = 11 (after n >>= 1, binary: 1011)

Iteration 2: Binary: 1011, checking rightmost bit

• n & 1 = 1 (rightmost bit is 1)
• Distance = cur - pre = 1 - inf (negative, won't update ans)
• ans = max(0, 1-inf) = 0
• pre = 1 (update previous 1's position)
• cur = 2, n = 5 (after shift, binary: 101)

Iteration 3: Binary: 101, checking rightmost bit

• n & 1 = 1 (rightmost bit is 1)
• Distance = cur - pre = 2 - 1 = 1
• ans = max(0, 1) = 1
• pre = 2 (update previous 1's position)
• cur = 3, n = 2 (after shift, binary: 10)

Iteration 4: Binary: 10, checking rightmost bit

• n & 1 = 0 (rightmost bit is 0)
• No action since bit is 0
• cur = 4, n = 1 (after shift, binary: 1)

Iteration 5: Binary: 1, checking rightmost bit

• n & 1 = 1 (rightmost bit is 1)
• Distance = cur - pre = 4 - 2 = 2
• ans = max(1, 2) = 2
• pre = 4 (update previous 1's position)
• cur = 5, n = 0 (after shift)

Loop ends as n = 0

Result: The maximum distance between adjacent 1s is 2, which corresponds to the gap between the 1s at positions 2 and 4 in the binary representation 10110.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the given integer. This is because the while loop continues as long as n > 0, and in each iteration, we right shift n by 1 bit (equivalent to dividing by 2). Since we're essentially counting the number of bits in the binary representation of n, and a number n has approximately log₂(n) bits, the loop runs O(log n) times.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables ans, pre, and cur, regardless of the input size. No additional data structures that grow with input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding "Adjacent" 1s

The Problem: Many developers initially interpret "adjacent 1s" as 1s that are directly next to each other (like 11 in binary), leading them to look for patterns where the distance would always be 1.

Why It Happens: The term "adjacent" in everyday language often means "next to each other," but in this problem, it means consecutive 1s in the sequence with any number of 0s between them.

Example of Incorrect Understanding:

# WRONG: Looking for directly neighboring 1s
def binaryGap_wrong(n: int):
    binary = bin(n)[2:]
    max_gap = 0
    for i in range(len(binary) - 1):
        if binary[i] == '1' and binary[i+1] == '1':
            max_gap = 1  # This would always be 1!
    return max_gap

Solution: Remember that "adjacent" here means consecutive occurrences of 1s in the bit sequence, not physically neighboring bits. The correct approach tracks positions of all 1s and measures distances between consecutive pairs.

Pitfall 2: Incorrect Initialization of Previous Position

The Problem: Initializing previous_one_position to 0 instead of infinity can cause incorrect results when the first 1 appears at position 0.

Why It Happens:

# WRONG initialization
previous_one_position = 0  # Problematic!
current_position = 0

# When first 1 is found at position 0:
# distance = 0 - 0 = 0 (incorrect, should not count)

Example Causing Issues:

• Input: n = 8 (binary: 1000)
• With previous_one_position = 0, when we find the 1 at position 3, we'd calculate distance as 3-0=3, which is wrong since there's only one 1.

Solution: Initialize to float('inf') so the first distance calculation yields a negative number (which won't affect the maximum) and ensures we only start counting distances after finding at least two 1s.

Pitfall 3: Using String Conversion Instead of Bit Manipulation

The Problem: Converting to binary string and then processing can be less efficient and more error-prone.

Why It Happens:

# Less efficient approach
def binaryGap_string(n: int):
    binary = bin(n)[2:]  # Creates string allocation
    positions = []
    for i, bit in enumerate(binary):
        if bit == '1':
            positions.append(len(binary) - 1 - i)  # Easy to mess up indexing!
    # ... rest of logic

Issues with String Approach:

• Extra memory allocation for string
• Confusion with indexing (left-to-right vs right-to-left)
• Need to handle string slicing ([2:] to remove '0b' prefix)

Solution: Stick with bit manipulation using n & 1 and n >>= 1 for cleaner, more efficient code that directly works with the binary representation without conversion overhead.