Binary Gap

Bit Manipulation

15 min

Problem Statement

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.

Example

Example 1:

Input: n = 22

Output: 2

Explanation: The binary representation of 22 is 10110. The first pair of adjacent 1's has a distance of 2. The second pair has a distance of 1. The answer is the largest of these, 2.

Solution (One Pass)

We can solve this by iterating through the bits of the number while keeping track of the last position we saw a '1'.

Algorithm Steps

Initialize max_distance = 0 and last_position = -1.
Iterate through the bits of the number from 0 to 31.
If the current bit is a '1':
If last_position is not -1 (meaning we've seen a '1' before), calculate the distance from the current position to the last_position.
Update max_distance with the maximum distance found so far.
Update last_position to the current bit's index.
Return max_distance.

Number:

Binary Representation

Last '1' Position

None

Max Distance

Initial number: 22 (00010110)

Binary Gap Solution


class Solution:
    def binaryGap(self, n: int) -> int:
        last_position = -1
        max_distance = 0
        for i in range(32):
            if (n >> i) & 1:
                if last_position != -1:
                    max_distance = max(max_distance, i - last_position)
                last_position = i
        return max_distance