OddOccurrencesInArray – Codility – Solution

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]