OddOccurrencesInArray – Codility – Solution

Category : Java | Sub Category : Java Programs from Coding Interviews | By Prasad Bonam Last updated: 2020-12-21 03:44:13 Viewed : 561


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.

1
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
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 - should1ve return unpaired value by now");
  }
}

TestNG test cases for this problem which all passed:

1
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
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 [] { 9393979 },  7 },
      new Object [] { new int [] { 1213523 },  5 },

      //double pair matching
      new Object [] { new int [] { 12135231122 },  5 },
     
      //large numbers
      new Object [] { new int [] { 100000020000001000000300000005000000200000030000000 },  5000000 },
    };
  }

  @Test(dataProvider = "test1")
  public void verifySolution(int [] pA, int pExpectedNonPair) {
    Assert.assertEquals(solution.solution(pA), pExpectedNonPair);
  }
}

Search
Related Articles

Leave a Comment: