Infinite while loop while counting binary gap

Question

I'm currently working on solving the binary gap problem (counting the number of 0's between two 1's, and returning the largest gap of 0's found), my solution first starts off with converting the integer N into a string of N's binary form, which works fine.

Conceptually what I'm doing (or at least think I'm doing) was counting the 0's until I reach a 1 character, which is then compared to the current count of 0's under the variable gap, I then would zero out my zero counter zero_count, and I also added an if statement to check for the case of it reaching the end of the binary string, returning 0 if no and 1 if found.

For some reason I'm getting an infinite loop, and I think I've narrowed it down to the index value not incrementing, and I'm not sure why. If someone could explain I would greatly appreciate it!

This was done in Java.

import java.util.*;

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        String binary = "";

        int power = 31;

        //double expo = Math.pow(2,power);
        while(power !=-1){
            if(N - Math.pow(2,power) > -1){
                binary += "1";
                N -= Math.pow(2,power);
            }
            else{binary += "0";}
            power--;
        }
        System.out.println(binary);
        
        //above works
        int  gap = 0;
        int zero_count = 0;
        int index = 0;
        for( int i = 0; i < binary.length(); i++){
            if(binary.charAt(i) == '1'){
                index= i+1;
                while(binary.charAt(index) =='0'){
                    index++;
                    zero_count++;
                    if(index == binary.length()-1){
                        return 0;
                    }
                }
            }
            if(zero_count > gap){
                gap = zero_count;
            zero_count = 0;
            }
            i = index;
        }
        return gap;
    }
}

user_12643162 · Answer

Too many loops..

added main to drive/run the code; you can remove the static on the method.

import java.util.*;

class Solution {
    public static void main(String[] args) {
            System.out.println("the max gap is: "+ Solution.solution(103241));
        }

    
    public static int solution(int N) {
        // write your code in Java SE 8
        String binary = "";

        int power = 31;

        //double expo = Math.pow(2,power);
        while(power !=-1){
            if(N - Math.pow(2,power) > -1){
                binary += "1";
                N -= Math.pow(2,power);
            }
            else{binary += "0";}
            power--;
        }
        System.out.println(binary);
        
        //above works
        int  max_gap = 0;
        int zero_count = 0;
        int index = 0;
        //boolean 
        for( int i = 0; i < binary.length(); i++){
            if(binary.charAt(i) == '0') {
                zero_count++;
            }
            else {
                if (zero_count > max_gap){
                    max_gap = zero_count;
                }
                zero_count = 0;
            }           
        }
        return max_gap;
    }
}

user_13279831 · Answer

There are several issues in the nested while loop:

it should check for the length of binary when comparing a character at index to avoid StringOutOfBoundsException
it should not return 0 when reaching the end of the string - the result can be incorrect
index should be decremented upon leaving the while loop
leading 0s should be skipped altogether to avoid infinite loop Also, there are issues with building binary string:
it does not convert negative numbers properly That being said, the following code resolves the mentioned issues:

public static int solution(int N) {
    // write your code in Java SE 8
    String binary = "";

    if (N == 0) {
        binary = "0"; // shortcut for 0
    } else {
        N &= Integer.MAX_VALUE; // remove sign bit for negative numbers
        while(N != 0) {
            binary = (N & 1) + binary; // get rid of leading zeros
            N >>= 1;
        }
    }
    
    //above works
    int gap = 0;
    int zero_count = 0;
    
    for (int i = 0, len = binary.length(); i < len; i++) {
        if (binary.charAt(i) == '1') {
            i++;
            while (i < len && binary.charAt(i) == '0') {
                zero_count++;
                if (i == len - 1) {
                    zero_count = 0;
                }
                i++;
            }
            i--;
        }
        if (zero_count > gap) {
            gap = zero_count;
            zero_count = 0;
        }
    }

    return gap;
}

However, a simpler solution may be implemented using the following facilies available in Java 8:

Integer::toBinaryString to get a binary string without leading zeroes
String::replaceAll to remove trailing zeroes
Pattern::splitAsStream to split the remaining string by 1 and get Stream
common Stream API mapToInt, max to get the maximal length of substrings consisting of zeroes only:

static int maxZeroGap(int n) {
    return Pattern.compile("1")
        .splitAsStream(
            Integer.toBinaryString(n).replaceAll("0+$", "")
        )
        .mapToInt(String::length)
        .max()
        .orElse(0);
}

Tests:

int[] nums = {
    0, 1, -1, -1023, Integer.MIN_VALUE, 0b10, 0b11, 0b101, 0b1001, 0b100101, 0b101000, 0b1000000100001
};
for (int i : nums) {
    System.out.printf("%d -> %s%n", i, Integer.toBinaryString(i));
    int z = maxZeroGap(i);
    System.out.println("max zeros = " + z + "; solution=" + solution(i));
    System.out.println("--------------------");
}

Output

0 -> 0
max zeros = 0; solution=0
--------------------
1 -> 1
max zeros = 0; solution=0
--------------------
-1 -> 11111111111111111111111111111111
max zeros = 0; solution=0
--------------------
-1023 -> 11111111111111111111110000000001
max zeros = 9; solution=9
--------------------
-2147483648 -> 10000000000000000000000000000000
max zeros = 0; solution=0
--------------------
2 -> 10
max zeros = 0; solution=0
--------------------
3 -> 11
max zeros = 0; solution=0
--------------------
5 -> 101
max zeros = 1; solution=1
--------------------
9 -> 1001
max zeros = 2; solution=2
--------------------
37 -> 100101
max zeros = 2; solution=2
--------------------
40 -> 101000
max zeros = 1; solution=1
--------------------
4129 -> 1000000100001
max zeros = 6; solution=6
--------------------

Infinite while loop while counting binary gap

2 Answers