2.2 - Odd occurrences in an array

Odd Occurrences in an Array

Problem

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the next slide.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];

each element of array A is an integer within the range [1..1,000,000,000];

all but one of the values in A occur an even number of times.

Example

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9

A[3] = 3 A[4] = 9 A[5] = 7

A[6] = 9

the elements at indexes 0 and 2 have value 9,

the elements at indexes 1 and 3 have value 3,

the elements at indexes 4 and 6 have value 9,

the element at index 5 has value 7 and is unpaired.

Trick: Use of Key-Value Pair and a Set

The Key-Value pair in the heading could be a dictionary (dict) in Python (or HashMap in Java).

We would need to traverse the input array once and maintain two data structures (a dict and a set).

Dict named counts: would contain the elements as keys

Set named odds: would contain the elements whose number of occurrences are found to be odd.

Note during the program’s lifetime, size of set ‘odds’ would change but by the end of iteration, there would be only one element in it.

Java Based Code of a Variant of The Solution From My Friend Rohit

import java.util.*; 
class Solution { 
 public int solution(int[] A) { 
  Map<Integer, Integer> integerMap = new HashMap<Integer, Integer>(); 
  for (int i = 0; i < A.length; A++)) {
   if (!integerMap.containsKey(A[i])) { 
    integerMap.put(A[i], 1); 
   } 
   else { 
    int count = integerMap.get(A[i]);      	 
    integerMap.put(A[i], count + 1); 
  }
  int missingNumber = 0; 
  for (Map.Entry<Integer, Integer> map : integerMap.entrySet()) 
  { 
   if (map.getValue() % 2 == 1) { 
    missingNumber = map.getKey(); 
  } 
  return missingNumber; 
 }
}  

In Python Code

def solution(A):
    counts = dict()
    odds = set()

    for i in A:
        if i in counts:
            counts[i] += 1
        else:
            counts[i] = 1

        if counts[i] % 2 == 1:
            odds.add(i)
        else:
            odds.remove(i)

    return odds.pop()  

Time Complexity

Detected time complexity:

O(N) or O(N*log(N))

Test Cases

-simple1

simple test n=5

-extreme_single_item

[42]

-small1

small random test n=201

- medium1

medium random test n=2,001

big1

big random test n=999,999, multiple repetitions

-big2

big random test n=999,999

Tags: Technology,Algorithms,