Java solution to Codility MissingInteger problem (Lesson 4 – Counting Elements) which scored 100%. The problem is to find the smallest positive integer that does not occur in a given array. The main strategy is to use two java.util.TreeSets, which order their elements: 1) a perfect set and 2) the actual set and check for the missing element in the actual set that exists in the perfect set.
[cc lang="java" escaped="true"] package com.codility.lesson04.countingelements; import java.util.Set; import java.util.TreeSet; public class MissingInteger { public int solution(int[] A) { Set testedSet = new TreeSet(); Set perfectSet = new TreeSet(); for(int i=0; i<A.length; i++) { testedSet.add(A[i]); //convert array to set to get rid of duplicates, order int's perfectSet.add(i+1); //create perfect set so can find missing int } for(int current : perfectSet) { if(!testedSet.contains(current)) { return current; } } if(perfectSet.size() == testedSet.size()) { return perfectSet.size() + 1; //e.g. {1, 2, 3} should return 4 } return 1; //default - e.g. if A array has negative values or just a single positive value like 10 } } [/cc]
TestNG test cases for this problem which all passed:
[cc lang="java" escaped="true"] package test.com.codility.lesson04.countingelements; import org.testng.Assert; import org.testng.annotations.*; import com.codility.lesson04.countingelements.MissingInteger; public class MissingIntegersTests { private MissingInteger solution; @BeforeTest public void setUp() { solution = new MissingInteger(); } @DataProvider(name = "test1") public Object [][] createData1() { return new Object [][] { new Object [] { new int [] { 1, 3, 6, 4, 1, 2 }, 5 }, new Object [] { new int [] { 1, 3, 6, 4, 1, 2, 5 }, 7 }, new Object [] { new int [] { 1, 2, 3 }, 4 }, new Object [] { new int [] { -1,-3 }, 1 }, new Object [] { new int [] { -1,-3, 2 }, 1 }, new Object [] { new int [] { -1,-3, 1 }, 2 }, new Object [] { new int [] { 0 }, 1 }, new Object [] { new int [] { -1000000 }, 1 }, new Object [] { new int [] { -1000000, 1 }, 2 }, new Object [] { new int [] { 1000000 }, 1 }, new Object [] { new int [] { 999999, 999998, 1000000 }, 1 }, new Object [] { new int [] { 1, 3, 999999, 999998, 1000000 }, 2 }, }; } @Test(dataProvider = "test1") public void verifySolution(int [] pA, int pExpected) { Assert.assertEquals(solution.solution(pA), pExpected); } } [/cc]