Find Even Occurring Element

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

Solution 1: We can use a hashtable as we always do with problems that involve counting. Scan the array and count the occurrences of each number. Then perform a second pass from the hashtable and return the element with even count.

Solution 2: We can use XOR trick for this problem. First we get all the unique numbers in the array using a set in O(N) time. Then we XOR the original array and the unique numbers all together. Result of XOR is the even occurring element. Because every odd occurring element in the array will be XORed with itself odd number of times, therefore producing a 0. And the only even occurring element will be XORed with itself even number of times, which is the number itself. The order of XOR is not important. The conclusion is that if we XOR a number with itself odd number of times we get 0, otherwise if we XOR even number of times then we get the number itself. And with multiple numbers, the order of XOR is not important, just how many times we XOR a number with itself is significant.

For example, let’s say we’re given the following array: [2, 1, 3, 1]. First we get all the unique elements [1, 2, 3]. Then we construct a new array from the original array and the unique elements by appending them together [2, 1, 3, 1, 1, 2, 3]. We XOR all the elements in this new array. The result is 2^1^3^1^1^2^3 = 1. Because the numbers 2 and 3 occur in the new array even number of times (2 times), so they’ll be XORed with themselves odd times (1 time), which results in 0. The number 1 occurs odd number of times (3 times), so it’ll be XORed with itself even times (2 times), and the result is the number 1 itself. Which is the even occurring element in the original array.