## OddOccurrencesInArray – Codility – Solution

Category : Java | Sub Category : Java Programs from Coding Interviews | By Runner Dev Last updated: 2020-12-21 09:14:13 Viewed : 199

# 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 - should1ve 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);  }}
```

##### Related Articles 