Scale Engineer

Binary Gap

Easy
#0822Time: 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: O(1). This approach only uses a few integer variables to store state, regardless of the size of `n`.2 companies
Patterns
Bit Manipulation
Companies
eBayX

Prompt

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 <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1). This approach only uses a few integer variables to store state, regardless of the size of `n`.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem