Java solution to Codility OddOccurrencesInArray problem (Lesson 2 – Arrays) which scored 100%. The problem is to find the single unpaired element in an odd numbered integer array. A brute force method will take too long so I had to find a more creative solution.
The main strategy is to use a hash table to store the occurrence counter of each number, then check all keys for first odd numbered occurrence counter.
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
import java.util.HashMap;
import java.util.Set;
public class OddOccurrencesInArray {
public int solution(int[] A) {
HashMap <Integer, Integer> occurrencesMap = new HashMap<Integer, Integer>();
for(int i=0; i<A.length; i++) {
if(occurrencesMap.containsKey(A[i])) {
int occurrences = occurrencesMap.get(A[i]);
occurrences++;
occurrencesMap.put(A[i], occurrences); //increment occurrence counter and store it
}
else {
occurrencesMap.put(A[i], 1); //1st occurrences of this value
}
}
Set keySet = occurrencesMap.keySet();
for(int currentKey : keySet) {
int occurrences = occurrencesMap.get(currentKey);
//if occurs odd number of times, we found the unpaired value - no need to continue checking
if(occurrences % 2 != 0) return currentKey;
}
//should never get to here
throw new RuntimeException("shouldn't get to here - should've return unpaired value by now");
}
}
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
import org.testng.Assert;
import org.testng.annotations.*;
import com.codility.lesson02.arrays.OddOccurrencesInArray;
public class OddOccurrencesInArrayTests {
private OddOccurrencesInArray solution;
@BeforeTest
public void setUp() {
solution = new OddOccurrencesInArray();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { new int [] { 9, 3, 9, 3, 9, 7, 9 }, 7 },
new Object [] { new int [] { 1, 2, 1, 3, 5, 2, 3 }, 5 },
//double pair matching
new Object [] { new int [] { 1, 2, 1, 3, 5, 2, 3, 1, 1, 2, 2 }, 5 },
//large numbers
new Object [] { new int [] { 1000000, 2000000, 1000000, 30000000, 5000000, 2000000, 30000000 }, 5000000 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int [] pA, int pExpectedNonPair) {
Assert.assertEquals(solution.solution(pA), pExpectedNonPair);
}
}