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.
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.
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.
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.
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.
Convert the number to a binary string manually, store indices of '1's, calculate gaps, and keep track of the largest gap found.
Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.
We use two pointers pre and cur to represent the positions of the previous and current 1 bits, respectively. Initially, pre = 100 and cur = 0. Then, we traverse the binary representation of n. When we encounter a 1, we calculate the distance between the current position and the previous 1 position and update the answer.
The time complexity is O(log n), where n is the given integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Convert to Binary and Find Gaps | Time Complexity: O(log n) — The number of iterations is proportional to the number of bits, which is log2(n). |
| Approach 2: String Conversion Method | Time Complexity: O(log n) |
| Bit Manipulation | — |
| 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 |
Binary Gap | Two Simple Approaches | Leetcode 868 | codestorywithMIK • codestorywithMIK • 4,603 views views
Watch 9 more video solutions →Practice Binary Gap with our built-in code editor and test cases.
Practice on FleetCode