LeetCode 868: Binary Gap

Explanation

To solve this problem, we need to convert the given integer n into its binary representation and then iterate through the binary digits to find the longest distance between any two adjacent 1's.

1. Convert the integer n to its binary representation.
2. Iterate through the binary representation and keep track of the distance between adjacent 1's.
3. Update the maximum distance found so far.
4. Return the maximum distance as the result.

Time Complexity

The time complexity of this solution is O(log n) because we need to convert the integer n into its binary representation, which requires log n bits.

Space Complexity

The space complexity of this solution is O(log n) to store the binary representation of the integer n.

class Solution {
    public int binaryGap(int n) {
        String binary = Integer.toBinaryString(n);
        int maxDistance = 0;
        int lastOneIndex = -1;
        
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '1') {
                if (lastOneIndex != -1) {
                    maxDistance = Math.max(maxDistance, i - lastOneIndex);
                }
                lastOneIndex = i;
            }
        }
        
        return maxDistance;
    }
}