BinaryGap – Codility – Solution

Java solution to Codility BinaryGap problem (Lesson 1 – Iterations) which scored 100%. The problem is to find the longest sequence of zeros in a binary representation of an integer. The main strategy is:

• convert the integer to a binary string
• go through each character one by one and save the index of each 1 to a list
• go through the list of 1 indices and look for the largest difference in indices

[cc lang="java"  escaped="true"]
package com.codility.lesson01.iterations;

import java.util.ArrayList;
import java.util.List;

public class BinaryGap {
	public int solution(int N) {
		String binaryString = Integer.toBinaryString(N);
		
		int longestBinaryGap = 0;
		List onesList = new ArrayList();
		
		for(int i=0; i<binaryString.length(); i++) {
			if(binaryString.charAt(i) == '0') continue;
			onesList.add(i);
		}

		for(int i=0; i<onesList.size() - 1; i++) {
			//subtract 1 so that don't count 1's next to each other as having any gap
			int indicesDiff = onesList.get(i+1) - onesList.get(i) - 1;
			
			longestBinaryGap = Math.max(longestBinaryGap, indicesDiff);
		}
		return longestBinaryGap;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson01.iterations;

import org.testng.Assert;
import org.testng.annotations.*;

import com.codility.lesson01.iterations.BinaryGap;

public class BinaryGapTests {
	private BinaryGap solution;
	
	@BeforeTest
	public void setUp() {
		solution = new BinaryGap();
	}
	
	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] {          0,  0 },
			new Object [] {          9,  2 },
			new Object [] {         15,  0 },
			new Object [] {         32,  0 },
			new Object [] {        529,  4 },
			new Object [] {       1041,  5 },
			new Object [] {      65536,  0 },
			new Object [] {      65537, 15 },
			new Object [] {     100000,  4 }, 
			new Object [] {    2147483,  5 },
			new Object [] { 2147483637,  1 }, //max - 10
			new Object [] { 2147483646,  0 }, //max - 1
			new Object [] { 2147483647,  0 }  //max
		};
	}
	
	@Test(dataProvider = "test1")
	public void verifySolution(int pInput, int expectedBinaryGap) {
		Assert.assertEquals(solution.solution(pInput), expectedBinaryGap);
	}
}
[/cc]