Java Solution to Codility’s Binary Gap Problem

June 23, 2018

Hey Developer,

Codility is a great tool for practicing your problem solving skills. However, they do not provide you with solutions to their practice problems, which can definitely be frustrating at times. I hope my solutions can help you understand how to solve the problem in the least amount of time possible. This problem can be found here.

I am now going to explain how to convert from a decimal number to a binary number, which is what the while loop does in the code below. Let’s convert the number 10 into it’s binary representation.

10 / 2 = 5 with remainder of 0

5 / 2 = 2 with remainder of 1

2 / 2 = 1 with remainder of 0

1 / 2 = 0 with remainder of 1

Then, your binary representation of the number 10 is equal to 1010. The most significant bit (MSB) is the last bit you calculated, and the least significant bit (LSB) is the first bit you calculated. Below is the Java solution to the problem.

class Solution {
 
    public int solution(int N) {
    	// the longest binary string we need to handle in this problem is 31 bits
    	final int  MAX_STRING_LENGTH = 31;
    	// the biggest binary gap in our binary string 
    	int maxGapLength = 0;
    	// variable used for calculation of our binary string
    	int result = N;
    	// variable used for storing our binary String
    	StringBuilder binaryString = new StringBuilder(MAX_STRING_LENGTH);
 
    	// O(log N) loop for calculating our binary string
    	while (result > 0) {
    		// calculate each bit in the binary string and prepend it to the string (if we add it to the end, we would have to reverse the string after the loop)
    		binaryString.insert(0, result%2);
    		result = result / 2;	   	   		
    	}    	
 
    	int count = 0;
    	// loop through our binary string 
    	// O(log N)
    	for (int i = 0; i < binaryString.length(); i ++) {
    		// if we encounter a 0, then we increment our count variable
    		if (binaryString.charAt(i) == '0') {
    			count++;
    		}
    		// if we encounter a 1, then we are finished with our CURRENT gap
    		if (binaryString.charAt(i) == '1') {
    			// update our maxGapLength if needed
    			if (count > maxGapLength) {
    				maxGapLength = count;    				
    			}
    			// reset count variable so we can count the length of the next gap
    			count = 0;
    		}
    	}
 
        return maxGapLength;
    }
 
}