Binary Gap

Problem Statement

The task is to determine the longest distance between two adjacent 1s in the binary form of a given positive integer n. In the binary representation, two 1s are considered adjacent if there are only zeroes between them, though there could potentially be no zeroes (i.e., they might be right next to each other). We define the "distance" between these 1s as the number of bit positions between them. For instance, in the binary number 1001, the distance between the two 1s is 3. If there are no pairs of adjacent 1s in the binary representation, the function should return 0.

Examples

Example 1

Input:

n = 22

Output:

2

Explanation:

22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2

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.

Example 3

Input:

n = 5

Output:

2

Explanation:

5 in binary is "101".

Constraints

• 1 <= n <= 109

Approach and Intuition

To solve this problem, we can lay out the following step-by-step approach based upon understanding the binary conversion and distance measurement between bits:

1. Convert the given integer n to its binary representation. This can be ideally achieved using Python's built-in bin() function, which outputs the binary form prefixed with "0b".

2. Remove the "0b" prefix to simplify operations on the binary string.

3. Find positions of all 1s within the string. This can involve iterating through the string and recording indices where 1 occurs.

4. If less than two 1s are found, return 0 because no pairs of adjacent 1s exist.

5. Calculate distances between consecutive 1s. If you have indices of 1s, the distance between two consecutive 1s can be calculated as the difference in these indices.

6. Record and maintain the longest distance observed during these calculations.

7. At the end of these operations, return the recorded longest distance.

The primary intuition here is leveraging the straightforward binary representation to precisely map locations of 1s and efficiently calculate differences for distance determination. Given the problem's mention of maximum n (up to 109), it’s practical to opt for this direct approach due to its manageable size in terms of both computation and memory consumption. This method will employ linear time complexity relative to the bit length of n and use constant space for tracking indices and the maximum distance, aligning with the constraints provided.

Solutions

class Solution {
    public int maximumBinaryGap(int number) {
        int previous = -1, maxGap = 0;
        for (int index = 0; index < 32; ++index)
            if (((number >> index) & 1) > 0) {
                if (previous >= 0)
                    maxGap = Math.max(maxGap, index - previous);
                previous = index;
            }

        return maxGap;
    }
}