# 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.

```1234567891011121314151617181920212223242526272829303132package 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");
}
}

```

TestNG test cases for this problem which all passed:

```12345678910111213141516171819202122232425262728293031323334package 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);
}
}

```