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.
[cc lang="java" escaped="true"] package com.codility.lesson02.arrays; 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"); } } [/cc]
TestNG test cases for this problem which all passed:
[cc lang="java" escaped="true"] package test.com.codility.lesson02.arrays; 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); } } [/cc]