Binary Gap

EASY

Description

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.

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 <= 10⁹

Approaches

Checkout 3 different approaches to solve Binary Gap. Click on different approaches to view the approach and algorithm in detail.

Optimal Bit Manipulation

This is the most efficient approach. It avoids any string conversions and works directly with the bitwise representation of the integer. It iterates through the bits of the number, keeping track of the position of the last '1' found and calculating the distance to the current '1'.

Algorithm

Initialize maxDistance = 0, lastOneIndex = -1 (a sentinel value), and currentIndex = 0.
Loop while n > 0.
Check if the least significant bit of n is 1 (i.e., (n & 1) == 1).
If it is 1: a. If lastOneIndex is not -1, calculate distance = currentIndex - lastOneIndex. b. Update maxDistance = max(maxDistance, distance). c. Update lastOneIndex = currentIndex.
Right-shift n by 1 (n >>= 1) to process the next bit.
Increment currentIndex.
After the loop terminates, return maxDistance.

This method processes the number bit by bit, typically from right to left (least significant to most significant).

We use a loop that continues as long as n is greater than 0. In each iteration, we examine the rightmost bit and then right-shift the number to process the next bit.

We need variables to track the maxDistance, the currentIndex (or bit position), and the lastOneIndex.

The loop proceeds as follows:

Check if the rightmost bit is a 1 using the bitwise AND operator (n & 1).
If it is a 1, and we have seen a 1 before (lastOneIndex != -1), we calculate the distance currentIndex - lastOneIndex and update maxDistance. Then, we update lastOneIndex to currentIndex.
We then right-shift n (n >>= 1) to discard the bit we just processed.
We increment currentIndex to move to the next bit position.

This process continues until n becomes 0, meaning all bits have been checked. This approach uses only a constant amount of extra space.

class Solution {
    public int binaryGap(int n) {
        int lastOneIndex = -1;
        int maxDistance = 0;
        int currentIndex = 0;
        while (n > 0) {
            if ((n & 1) == 1) { // Check rightmost bit
                if (lastOneIndex != -1) {
                    maxDistance = Math.max(maxDistance, currentIndex - lastOneIndex);
                }
                lastOneIndex = currentIndex;
            }
            n >>= 1; // Right shift to process next bit
            currentIndex++;
        }
        return maxDistance;
    }
}

Complexity Analysis

Time Complexity: O(log n). The loop runs for each bit of the number `n`. Since `n` is a 32-bit integer in Java, the loop runs at most 32 times. More generally, it's proportional to the number of bits, which is `log n`.Space Complexity: O(1). This approach only uses a few integer variables to store state, regardless of the size of `n`.

Pros and Cons

Pros:

Most optimal in terms of space, using only O(1) extra space.
Very efficient in terms of time, as it avoids the overhead of string creation and manipulation.

Cons:

Might be slightly less intuitive for those not comfortable with bitwise operations.

Code Solutions

Checking out 3 solutions in different languages for Binary Gap. Click on different languages to view the code.

class Solution {
public
  int binaryGap(int n) {
    int ans = 0;
    for (int i = 0, j = -1; n != 0; ++i, n >>= 1) {
      if ((n & 1) == 1) {
        if (j != -1) {
          ans = Math.max(ans, i - j);
        }
        j = i;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Binary Gap

Patterns:

Bit Manipulation

Companies:

eBay |X |