Solution Explanation: Binary Gap

The problem asks to find the longest distance between any two adjacent 1s in the binary representation of a given integer n. The distance is the number of 0s between the two 1s.

Approach

The most efficient approach uses bit manipulation. We iterate through the bits of the integer, keeping track of the index of the previous occurrence of a 1 (pre) and the current index (cur).

1. Initialization: We initialize ans (the maximum distance) to 0, pre to a large value (e.g., 100 or infinity depending on the language) signifying no previous 1 has been encountered, and cur to 0.

2. Iteration: We iterate through the bits of n using a bitwise AND operation (n & 1) to check if the least significant bit is 1. We also right-shift n (n >>= 1) in each iteration to move to the next bit.

3. Finding 1s: If a 1 is encountered:

   • We calculate the distance cur - pre.
   • We update ans to be the maximum of ans and the calculated distance.
   • We update pre to the current index cur.

4. Updating Index: In each iteration, we increment cur to track the current bit position.

5. Return Value: After iterating through all bits, ans holds the longest distance between adjacent 1s. If no adjacent 1s are found, ans remains 0.

Time and Space Complexity

• Time Complexity: O(log n). The number of iterations is proportional to the number of bits in the binary representation of n, which is approximately log₂(n).
• Space Complexity: O(1). We use a constant number of variables to store the indices and the maximum distance.

Code Examples (with explanations inline)

Python:

class Solution:
    def binaryGap(self, n: int) -> int:
        ans = 0  # Initialize the maximum distance
        pre = float('inf')  # Initialize previous 1's index to infinity
        cur = 0  # Initialize current index
 
        while n:  # Iterate while n is not zero
            if n & 1:  # Check if the least significant bit is 1
                ans = max(ans, cur - pre)  # Update maximum distance
                pre = cur  # Update previous 1's index
            cur += 1  # Increment current index
            n >>= 1  # Right-shift n to move to the next bit
 
        return ans

Java:

class Solution {
    public int binaryGap(int n) {
        int ans = 0;
        int pre = 100; // Initialize previous 1's index to a large value
        int cur = 0;
 
        while (n != 0) {
            if ((n & 1) == 1) { // Check if the least significant bit is 1
                ans = Math.max(ans, cur - pre);
                pre = cur;
            }
            cur++;
            n >>= 1; // Right-shift n
        }
        return ans;
    }
}

The other languages (C++, Go, TypeScript, Rust) follow a very similar structure, adapting the syntax and specific functions (like max) accordingly. The core logic remains the same.