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 <= 109The key idea in #868 Binary Gap is to analyze the binary representation of a given integer and determine the maximum distance between two consecutive 1 bits. A practical approach is to scan the bits of the number while keeping track of the index of the last seen 1. Whenever another 1 is encountered, compute the distance between the current index and the previous one, and update the maximum gap accordingly.
You can implement this using bit manipulation by repeatedly shifting the number to the right and checking the least significant bit using n & 1. Alternatively, converting the number to a binary string and iterating through it can make the logic easier to visualize. The bit manipulation approach is typically preferred in interviews because it avoids extra memory usage.
Since the number of bits in an integer grows logarithmically with its value, the algorithm runs in O(log N) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit Manipulation (bit shifting and tracking indices) | O(log N) | O(1) |
| Binary String Traversal | O(log N) | O(log N) |
NeetCode
This approach involves converting the number into its binary representation and then finding the positions of '1's. We will iterate through the binary string, keep track of the last position where a '1' was found, and calculate the distance from the current '1' to the last. Record the maximum distance found.
Time Complexity: O(log n) — The number of iterations is proportional to the number of bits, which is log2(n).
Space Complexity: O(1) — Only a few variables are used.
1#include <stdio.h>
2#include <math.h>
3
4int binaryGap(int n) {
5 int lastPosition = -1, maxGap
We use bitwise operations to track positions of '1's in the binary form of 'n'. Each time a '1' is encountered, compare the current index with the last position of '1' to update the maximum gap. Shift bit to the right after each check until 'n' is 0.
This approach involves converting the integer to its binary string representation, iterating through the string to find indices of '1's, and calculating and storing the distances between consecutive '1's to find the maximum gap.
Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Binary Gap–style problems are common in coding interviews because they test understanding of bit manipulation and binary representation. Variations of this concept may appear in interviews at tech companies and coding assessments.
No complex data structure is required for this problem. Simple variables to track positions and the current maximum gap are enough, making bit manipulation the most efficient technique.
The optimal approach scans the bits of the integer using bit manipulation. By tracking the index of the previous 1 bit and updating the maximum distance whenever another 1 appears, you can compute the gap efficiently in a single pass.
The time complexity is O(log N) because the algorithm processes each bit of the number once. Since integers contain a logarithmic number of bits relative to their value, the loop runs only for those bits.
Convert the number to a binary string manually, store indices of '1's, calculate gaps, and keep track of the largest gap found.