The question

Given an integer array, one element occurs even number of times and all others have odd occurrences. Find the element with even occurrences.

My answer

The first thing I thought of was using XOR, but then I realized that I am looking for the even number so it won’t actually work. My next idea was to use a hashtable:

1 – Start on the first elements and create a hashtable with the number of times each character is found

2 – Look for the even number in the hashtable

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
var a = [1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 4, 4];

function findEven(arr) {
  var hash = {};

  // Check all characters and add count to hash table
  for (var i = 0; i < arr.length; i++) {
    var key = arr[i];
    if (undefined === hash[key]) {
      hash[key] = 1;
    } else {
      hash[key]++;
    }
  }

  // Check the hash table for even element
  for (var k in hash) {
    if (0 === hash[k] % 2) {
      return parseInt(k, 10);
    }
  }
}

function test() {
  if (findEven(a) === 7) {
    console.log('success');
  }
}

test(); // Prints success

The complexity for this solution would be O(n) for creating the hash table and another O(n) for checking the hash table for the even element. At the end this is O(n).

[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming