Leetcode 868. Binary Gap
Problem Explanation
The given problem asks you to determine the maximum distance between two consecutive 1's
in the binary representation of an input number N
. If there are no consecutive 1's
, the function should return 0
.
For example, consider the positive integer 8
. In binary, 8
is represented as 1000
. Here, we don't have any pairs of consecutive 1's
, so the function would return 0
.
Now, consider the positive integer 22
. In binary, 22
is represented as 10110
. Here, we do have a pair of consecutive 1's
and the maximum distance between them is 2
.
To solve the problem, you can convert the input number to its binary representation and then iterate over the binary digits. For each 1
digit, calculate the distance from the previous 1
digit, and continuously update the maximum distance encountered.
Approach Explanation
The solution uses bitwise operations and a simple iteration to solve the problem.
-
It initializes a variable
d
to-32
which will keep track of the distance between any two1's
.-32
is chosen because the maximum possible distance can't be more than 32 as there are at most 32 bits in an integer. -
It then iteratively divides the number
n
by2
as a way of shifting the binary digits to the right, thus exploring each binary digit of the number. -
It also keeps incrementing the variable
d
which gives the distance to the next1
. -
When it encounters a
1
(n & 1
gives1
if the rightmost bit is1
,0
otherwise), it stores the maximum distance found so far and resetsd
to0
as it has encountered a1
.
As such, the solution does not use any special algorithms, data structures, or patterns. It simply makes use of bitwise operations and integer division.
Python Solution
1 2python 3class Solution: 4 def binaryGap(self, n: int) -> int: 5 ans = 0 6 7 # D := distance between any two 1's 8 # Initialized to a reasonable small value 9 for d in range(-32, 32): 10 if n == 0: 11 break 12 elif n & 1: 13 ans = max(ans, d) 14 d = 0 15 n = n // 2 16 17 return ans
Java Solution
1 2java 3public class Solution { 4 public int binaryGap(int n) { 5 int ans = 0; 6 7 // D := distance between any two 1's 8 // Initialized to a reasonable small value 9 for (int d = -32; n > 0; d++) { 10 if ((n & 1) == 1) { 11 ans = Math.max(ans, d); 12 d = 0; 13 } 14 15 n = n >> 1; 16 } 17 18 return ans; 19 } 20}
JavaScript Solution
1 2javascript 3class Solution { 4 binaryGap(n) { 5 let ans = 0; 6 7 // D := distance between any two 1's 8 // Initialized to a reasonable small value 9 for (let d = -32; n; n = Math.floor(n/2), d++) { 10 if (n & 1) { 11 ans = Math.max(ans, d); 12 d = 0; 13 } 14 } 15 16 return ans; 17 } 18};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int binaryGap(int n) { 6 int ans = 0; 7 8 // D := distance between any two 1's 9 // Initialized to a reasonable small value 10 for (int d = -32; n; n /= 2, d++) { 11 if (n & 1) { 12 ans = std::max(ans, d); 13 d = 0; 14 } 15 } 16 17 return ans; 18 } 19};
C# Solution
1 2csharp 3public class Solution { 4 public int BinaryGap(int n) { 5 int ans = 0; 6 7 // D := distance between any two 1's 8 // Initialized to a reasonable small value 9 for (int d = -32; n>0; d++) { 10 if ((n & 1) == 1) { 11 ans = Math.Max(ans, d); 12 d = 0; 13 } 14 15 n /= 2; 16 } 17 18 return ans; 19 } 20}
Time and Space Complexity Analysis
The time complexity for this solution is O(log(n)) because we are iterating through each bit of the input number, n. The number of bits in n is log(n). Therefore, the total time complexity is also O(log(n)).
The space complexity for the solution is O(1) because we do not use any data structure to store intermediate results. We only use a few integer variables that occupy constant space regardless of the input size.
Testing the solution
Conducting a few selected tests could sufficiently verify the solution.
For Python:
1
2python
3s = Solution()
4
5print(s.binaryGap(8)) # Expected: 0
6print(s.binaryGap(22)) # Expected: 2
For JavaScript:
1 2javascript 3var s = new Solution(); 4 5console.log(s.binaryGap(8)); // Expected: 0 6console.log(s.binaryGap(22)); // Expected: 2
For Java:
1
2java
3public static void main(String[] args) {
4 Solution s = new Solution();
5
6 System.out.println(s.binaryGap(8)); // Expected: 0
7 System.out.println(s.binaryGap(22)); // Expected: 2
8}
For C#:
1
2csharp
3class Program
4{
5 static void Main(string[] args)
6 {
7 Solution s = new Solution();
8
9 Console.WriteLine(s.BinaryGap(8)); // Expected: 0
10 Console.WriteLine(s.BinaryGap(22)); // Expected: 2
11 }
12}
For C++:
1
2cpp
3int main()
4{
5 Solution s;
6
7 std::cout << s.binaryGap(8) << "\n"; // Expected: 0
8 std::cout << s.binaryGap(22) << "\n"; // Expected: 2
9
10 return 0;
11}
In each case, the solution should match the expected output. If it doesn't, there's likely a logical error in the code that needs debugging.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.