Find a single integer that occurs with even frequency in a given array of ints when all others occur odd with frequency

Question

This is an interview question.

Given an array of integers, find the single integer value in the array which occurs with even frequency. All integers will be positive. All other numbers occur odd frequency. The max number in the array can be INT_MAX.

For example, [2, 8, 6, 2] should return 2.

the original array can be modified if you can find better solutions such as O(1) space with O(n) time.

I know how to solve it by hashtable (traverse and count freq). It is O(n) time and space.

Is it possible to solve it by O(1) space or better time?

Answer 1

If you are allowed to sort the original array, I believe that you can do this in O(n lg U) time and O(lg U) space, where U is the maximum element of the array. The idea is as follows - using in-place MSD radix sort, sort the array in O(n lg U) time and O(lg U) space. Then, iterate across the array. Since all equal values are consecutive, you can then count how many times each value appears. Once you find the value that appears an even number of times, you can output the answer. This second scan requires O(n) time and O(1) space.

If we assume that U is a fixed constant, this gives an O(n)-time, O(1)-space algorithm. If you don't assume this, then the memory usage is still better than the O(n) algorithm provided that lg U = O(n), which should be true on most machines. Moreover, the space usage is only logarithmically as large as the largest element, meaning that the practical space usage is quite good. For example, on a 64-bit machine, we'd need only space sufficient to hold 64 recursive calls. This is much better than allocating a gigantic array up-front. Moreover, it means that the algorithm is a weakly-polynomial time algorithm as a function of U.

That said, this does rearrange the original array, and thus does destructively modify the input. In a sense, it's cheating because it uses the array itself for the O(n) storage space.

Hope this helps!

Answer 2

Given this is an interview question, the answer is: O(1) space is achievable "for very big values of 1":

• Prepare a matcharray 1..INT_MAX of all 0
• When traversing the array, use the integer as an index into the matcharray, adding 1
• When done, traverse the match array to find the one entry with a positive even value

The space for this is large, but independent of the size of the input array, so O(1) space. For really big data sets (say small value range, but enormous array length), this might even be a practically valid solution.