Binary Gap

Problem

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 (possibly no 0’s). The distance between two 1’s is the absolute difference between their bit positions. For example, the two 1’s in "1001" have a distance of 3.

Examples

Example 1:

1
2
3
4
5
6
7

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "1̲01̲10" with a distance of 2.
The second adjacent pair of 1's is "101̲1̲0" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "1̲011̲0" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

1
2
3
4
5
6

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:

1
2
3

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

Solution

The task is to determine the longest distance between any two adjacent 1’s in the binary representation of a given positive integer ( n ).

Method 1 - Using Binary String

Here is the approach we can take:

1. Convert n to Binary: Obtain the binary representation of n.
2. Track Positions of 1s: Iterate through the binary string and record the positions of each 1.
3. Calculate Distances: Compute the distances between consecutive 1s and keep track of the maximum distance encountered.
4. Return Result: If fewer than two 1s are found, return 0. Otherwise, return the maximum distance.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int binaryGap(int n) {
        String binaryString = Integer.toBinaryString(n);
        int maxLength = 0;
        int previousIndex = -1;

        for (int i = 0; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == '1') {
                if (previousIndex != -1) {
                    int distance = i - previousIndex;
                    maxLength = Math.max(maxLength, distance);
                }
                previousIndex = i;
            }
        }

        return maxLength;
    }
}

Complexity

• Time: O(log n) for converting number n to binary string
• Space: O(1)