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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.
| 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) |
Reverse Bits - Binary - Leetcode 190 - Python • NeetCode • 146,976 views views
Watch 9 more video solutions →Practice Binary Gap with our built-in code editor and test cases.
Practice on FleetCode