Binary Gap
EasyPrompt
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), andcurrentIndex = 0. - Loop while
n > 0. - Check if the least significant bit of
nis 1 (i.e.,(n & 1) == 1). - If it is 1:
a. If
lastOneIndexis not -1, calculatedistance = currentIndex - lastOneIndex. b. UpdatemaxDistance = max(maxDistance, distance). c. UpdatelastOneIndex = currentIndex. - Right-shift
nby 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 distancecurrentIndex - lastOneIndexand updatemaxDistance. Then, we updatelastOneIndextocurrentIndex. - We then right-shift
n(n >>= 1) to discard the bit we just processed. - We increment
currentIndexto 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.
This approach first converts the integer n into its binary string representation. Then, it iterates through this string to find the positions of all the '1's and stores these positions in a list. Finally, it computes the differences between adjacent positions in the list to find the maximum gap.
Algorithm
- Convert the input integer
nto its binary string representation. - Create an empty list,
oneIndices, to store the indices of '1's. - Iterate through the binary string. If a character is '1', add its index to
oneIndices. - If the size of
oneIndicesis less than 2, return 0. - Initialize a variable
maxDistanceto 0. - Iterate through
oneIndicesfrom the first index up to the second-to-last index. - In each iteration, calculate the difference between the current index and the next index.
- Update
maxDistancewith this difference if it's larger than the currentmaxDistance. - Return
maxDistance.
Walkthrough
The core idea is to transform the problem from the domain of integers and bits to the domain of strings and characters, which can be easier to reason about.
First, we use a built-in function like Integer.toBinaryString(n) to get the binary representation of n.
We then create a list to hold the indices of all '1's. We iterate through the binary string, and whenever we encounter a '1', we add its index to our list.
After populating the list of indices, we check if it contains fewer than two elements. If it does, it means there are no adjacent '1's, so we return 0.
Otherwise, we iterate through the list of indices from the first element to the second-to-last element. In each step, we calculate the distance to the next index (indices.get(i+1) - indices.get(i)) and update our maximum distance found so far.
After the loop finishes, the variable holding the maximum distance will contain the answer.
import java.util.ArrayList;import java.util.List; class Solution { public int binaryGap(int n) { String binaryString = Integer.toBinaryString(n); List<Integer> oneIndices = new ArrayList<>(); for (int i = 0; i < binaryString.length(); i++) { if (binaryString.charAt(i) == '1') { oneIndices.add(i); } } if (oneIndices.size() < 2) { return 0; } int maxDistance = 0; for (int i = 0; i < oneIndices.size() - 1; i++) { int distance = oneIndices.get(i + 1) - oneIndices.get(i); if (distance > maxDistance) { maxDistance = distance; } } return maxDistance; }}Complexity
Time
O(log n). The number of bits in `n` is `log n`. Converting to a string, iterating through it, and iterating through the list of indices all take time proportional to `log n`.
Space
O(log n). We need space for the binary string (length `log n`) and the list of indices (which can have up to `log n` elements).
Trade-offs
Pros
Conceptually simple and easy to understand.
Leverages built-in string conversion functions, making the implementation straightforward.
Cons
Requires extra space to store the binary string and the list of indices. The space complexity is
O(log n), which is less optimal than other approaches.
This approach improves upon the previous one by avoiding the need to store all indices of '1's. It still converts the number to its binary string representation, but then it finds the maximum gap in a single pass over the string.
Algorithm
- Convert the input integer
nto its binary string representation. - Initialize
maxDistance = 0andlastOneIndex = -1. - Iterate through the binary string with index
i. - If the character at index
iis '1': a. Check iflastOneIndexis not -1. b. If it's not, calculatedistance = i - lastOneIndex. c. UpdatemaxDistance = max(maxDistance, distance). d. UpdatelastOneIndex = i. - After the loop, return
maxDistance.
Walkthrough
Similar to the first approach, we begin by converting n to its binary string using Integer.toBinaryString(n).
Instead of storing all indices, we only need to remember the index of the most recently seen '1'. We use a variable, say lastOneIndex, initialized to a sentinel value like -1.
We iterate through the binary string. When we find a '1', we check if lastOneIndex is valid (not -1). If it is, it means we have found an adjacent pair of '1's. We calculate the distance (currentIndex - lastOneIndex) and update our maxDistance.
Regardless of whether it was the first '1' or not, we update lastOneIndex to the current index.
This way, we only need a few variables to keep track of the state, reducing the auxiliary space complexity.
class Solution { public int binaryGap(int n) { String binaryString = Integer.toBinaryString(n); int maxDistance = 0; int lastOneIndex = -1; for (int i = 0; i < binaryString.length(); i++) { if (binaryString.charAt(i) == '1') { if (lastOneIndex != -1) { int distance = i - lastOneIndex; maxDistance = Math.max(maxDistance, distance); } lastOneIndex = i; } } return maxDistance; }}Complexity
Time
O(log n). The time is dominated by converting to a string and iterating through it, both of which are proportional to the number of bits.
Space
O(log n). Although the auxiliary space for variables is `O(1)`, the space required to store the binary string itself is `O(log n)`.
Trade-offs
Pros
More space-efficient than storing all indices. The auxiliary space is constant.
Still relatively easy to implement and understand.
Cons
Still relies on creating an intermediate string representation, which uses
O(log n)space.
Solutions
Solution
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; }}class Solution {public: int binaryGap(int n) { int ans = 0; for (int i = 0, j = -1; n; ++i, n >>= 1) { if (n & 1) { if (j != -1) ans = max(ans, i - j); j = i; } } return ans; }};class Solution: def binaryGap(self, n: int) -> int: ans, j = 0, - 1 for i in range(32): if n & 1: if j != - 1: ans = max(ans, i - j) j = i n >>= 1 return ansVideo 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.