Watch 10 video solutions for Binary Gap, a easy level problem involving Bit Manipulation. This walkthrough by codestorywithMIK has 4,603 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: You are given a positive integer n. Convert it to binary and return the longest distance between two consecutive 1 bits. The distance is measured by the difference in their positions. If there are fewer than two 1 bits, the result is 0.
The key observation: the binary representation determines the gaps. Once you know where each 1 appears, the problem reduces to tracking the maximum difference between consecutive positions. This is a classic bit manipulation exercise and appears frequently in entry-level coding interviews.
Approach 1: Convert to Binary and Find Gaps (O(log n) time, O(1) space)
Iterate through the bits of the number directly using bit operations. Repeatedly check the least significant bit using n & 1, then right shift with n >>= 1. Maintain the index of the last seen 1. Every time another 1 appears, compute the gap between the current index and the previous index, and update the maximum gap.
This method avoids creating a string or additional data structures. The loop runs once per bit of the number, which is proportional to log2(n). Space stays constant because only a few integer variables are tracked. This approach demonstrates practical use of bitwise operators and is the most natural solution when practicing bit manipulation problems.
Approach 2: String Conversion Method (O(log n) time, O(log n) space)
Convert the integer to its binary representation using built‑in utilities such as bin(n) in Python or Integer.toBinaryString(n) in Java. After conversion, iterate through the resulting string and record the positions of each '1'. For every new '1', compute the difference from the previous index and update the maximum gap.
This version trades a bit of memory for readability. The logic becomes straightforward because you operate on characters rather than individual bits. The time complexity is still O(log n) since the binary string length is proportional to the number of bits. Space complexity becomes O(log n) due to storing the binary string. This approach also touches concepts related to string processing.
Recommended for interviews: The bit‑iteration approach is usually preferred. Interviewers expect you to recognize that binary gaps depend only on bit positions and can be solved with simple shifts and bit checks. The string method is acceptable and easy to implement, but the bit manipulation version demonstrates stronger understanding of binary representation and space optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Binary and Scan Bits | O(log n) | O(1) | Best for interviews and optimal memory usage using bitwise operations |
| String Conversion Method | O(log n) | O(log n) | Simpler implementation when readability is preferred over strict space optimization |