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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
  }
}

TestNG test cases for this problem which all passed:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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);
  }
}