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.

1. It initializes a variable d to -32 which will keep track of the distance between any two 1'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.

2. It then iteratively divides the number n by 2 as a way of shifting the binary digits to the right, thus exploring each binary digit of the number.

3. It also keeps incrementing the variable d which gives the distance to the next 1.

4. When it encounters a 1 (n & 1 gives 1 if the rightmost bit is 1, 0 otherwise), it stores the maximum distance found so far and resets d to 0 as it has encountered a 1.

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.