Programming Challenge: Binary Zero Gap

3. Binary Zero Gap

Problem Statement: Given a positive integer, find the longest sequence of zeros in its binary representation that is bounded by ones at both ends.

Function Signature:

public int findLongestZeroGap(int number);

Examples:

Input: 1041 (binary "10000010001")
Output: 5 (sequence of 5 zeros between the first and third '1')
Input: 32 (binary "100000")
Output: 0 (no trailing '1' to bound the zeros)
Input: 529 (binary "1000010001")
Output: 4 (two gaps exist: 4 and 3 zeros, the longest is 4)

Key Concepts

This problem tests your understanding of:

Binary number representation
String manipulation
Loop control structures
Conditional logic
Algorithm optimization

Approach

Here's a step-by-step solution strategy:

Convert to Binary: Transform the integer into its binary string representation
Initialize Trackers: Set up variables to track the current and maximum gap lengths
Scan the String: Iterate through each character of the binary string
Count Zeros: When between '1's, count consecutive '0's
Update Maximum: Compare and store the longest valid sequence found

Solution Code

public class BinaryGapFinder {
    public static int findLongestZeroGap(int number) {
        String binary = Integer.toBinaryString(number);
        int maxGap = 0;
        int currentGap = 0;
        boolean betweenOnes = false;
        
        for (char bit : binary.toCharArray()) {
            if (bit == '1') {
                if (betweenOnes) {
                    maxGap = Math.max(maxGap, currentGap);
                    currentGap = 0;
                }
                betweenOnes = true;
            } else {
                if (betweenOnes) {
                    currentGap++;
                }
            }
        }
        
        return maxGap;
    }

    public static void main(String[] args) {
        System.out.println(findLongestZeroGap(1041));  // Output: 5
        System.out.println(findLongestZeroGap(32));    // Output: 0
        System.out.println(findLongestZeroGap(529));   // Output: 4
    }
}

Code Explanation

Binary Conversion

Integer.toBinaryString() converts the number to its binary representation (e.g., 1041 → "10000010001")

Tracking Variables

maxGap stores the longest sequence found, while currentGap counts zeros in the current sequence

State Flag

betweenOnes becomes true after the first '1' is encountered, enabling zero counting

Loop Logic

When a '1' appears, it either starts a new potential gap (if first '1') or finalizes the current gap measurement

Alternative Solutions

Bit Manipulation Approach: (More efficient, doesn't use string conversion)

public static int findLongestZeroGap(int number) {
    number >>>= Integer.numberOfTrailingZeros(number);
    int maxGap = 0;
    int currentGap = 0;
    
    while (number != 0) {
        if ((number & 1) == 1) {
            maxGap = Math.max(maxGap, currentGap);
            currentGap = 0;
        } else {
            currentGap++;
        }
        number >>>= 1;
    }
    return maxGap;
}

Complexity Analysis

Approach	Time Complexity	Space Complexity
String Conversion	O(log N)	O(log N)
Bit Manipulation	O(log N)	O(1)

←→