When working with binary numbers, we often look for patterns in the bits. One interesting and common coding puzzle is finding the longest binary gap. A binary gap is defined as the length of the longest consecutive sequence of zeros that is completely surrounded by ones on both sides.

For instance, consider the decimal number 9. In binary, 9 is represented as 1001. Here, we have a sequence of two zeros sandwiched between two ones, giving us a binary gap of 2. Now consider the number 20, which is 10100 in binary. There is a single zero between the first two ones, which represents a gap of 1. The two trailing zeros at the end do not count because they aren't followed by a closing 1. Finding these gaps efficiently is a great exercise in bit manipulation and array traversal.

Visualizing Binary Gap Sequence
Real-World Analogy: Counting Missing Fence Boards

Think of this problem like walking along a long wooden privacy fence. The solid vertical fence posts represent the binary digit 1, while the sections with missing boards represent the binary digit 0.

As you walk, you want to count the number of missing boards in each gap. If you start at a post, walk past three empty spots, and then reach another solid post, you have successfully measured a gap of 3. But if the fence ends while you are still walking past empty spots, that section doesn't count. A gap must have a starting post and an ending post to be considered complete.

The Algorithmic Design

To solve this problem programmatically in Java, we need a way to inspect the binary representation of a number. Here is the step-by-step logic:

  1. Convert to Binary String: We can convert our decimal integer N into its binary string representation using Java's built-in helper method, Integer.toBinaryString(N).
  2. Scan the Characters: We iterate through the binary string character by character (or convert it to a character array).
  3. Track Positions of '1's: The key to measuring gaps is keeping track of where the last '1' occurred. We can initialize a pointer or index tracker to store the position of the first '1'.
  4. Calculate Gap Sizes: Every time we encounter a subsequent '1', we can calculate the distance between the current index and the last seen '1' index. The gap size is simply the difference between the two indices minus one.
  5. Update the Maximum: If the calculated gap is larger than any gap we've seen so far, we update our maximum gap variable.
  6. Advance the Tracker: Finally, we update our tracker to point to the current '1' index, which becomes the new starting boundary for the next potential gap.

Step-by-Step Execution Walkthrough

Let's trace this logic with the number 137. In binary, 137 is 10001001.

  • Start: We initialize our maximum gap variable to 0. We locate the first occurrence of '1' at index 0, setting our last seen tracker to 0.
  • Indices 1, 2, 3: These indices contain zeros, so we continue scanning.
  • Index 4: We find another '1'. The gap is calculated as 4 - 0 - 1 = 3. Since 3 is greater than our maximum gap (which was 0), we update the maximum gap to 3. We update our last seen tracker to index 4.
  • Indices 5, 6: These contain zeros, so we continue.
  • Index 7: We hit a final '1'. The gap is 7 - 4 - 1 = 2. Since 2 is not larger than our current maximum gap of 3, the maximum remains 3. We update our tracker to 7.
  • Termination: The loop finishes, and we return our maximum gap of 3.

Implementation in Java

Here is the complete Java implementation of this algorithm. The code converts the integer into a binary string and loops through it, keeping track of indices to measure gaps.

package io.practise.myPractice;
 
import java.util.Scanner;
 
public class BinaryGapCodility {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        BinaryGapCodility output = new BinaryGapCodility();
        int gap = output.solution(N);
        System.out.println(gap);
    }
 
    public int solution(int N) {
        String str = Integer.toBinaryString(N);
        char[] arr = str.toCharArray();
 
        int o = 0;
        int large = 0;
 
        for (int t = 1; t < str.length(); t++) {
            if (arr[t] == '1') {
                int temp = t - o - 1;
                if (temp > large) {
                    large = temp;
                }
                o = t;
            }
        }
        return large;
    }
}

Conclusion & Complexity Analysis

This single-pass approach is highly efficient. The time complexity is O(log N) because the number of digits in the binary representation of N is proportional to log N (base 2). Since we only iterate through the binary string once, the algorithm runs in linear time relative to the number of bits. The space complexity is also kept minimal at O(log N) to store the string and character array, making it an optimal solution for coding interviews.