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
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
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:
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
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);
}
}