Find a number with even number of occurrences

Question

Given an array where number of occurrences of each number is odd except one number whose number of occurrences is even. Find the number with even occurrences.

e.g.

1, 1, 2, 3, 1, 2, 5, 3, 3

Output should be:

2

The below are the constraints:

1. Numbers are not in range.
2. Do it in-place.
3. Required time complexity is O(N).
4. Array may contain negative numbers.
5. Array is not sorted.

With the above constraints, all my thoughts failed: comparison based sorting, counting sort, BST's, hashing, brute-force.

I am curious to know: Will XORing work here? If yes, how?

Answer 1

This problem has been occupying my subway rides for several days. Here are my thoughts.

If A. Webb is right and this problem comes from an interview or is some sort of academic problem, we should think about the (wrong) assumptions we are making, and maybe try to explore some simple cases.

The two extreme subproblems that come to mind are the following:

• The array contains two values: one of them is repeated an even number of times, and the other is repeated an odd number of times.
• The array contains n-1 different values: all values are present once, except one value that is present twice.

Maybe we should split cases by complexity of number of different values.

If we suppose that the number of different values is O(1), each array would have m different values, with m independent from n. In this case, we could loop through the original array erasing and counting occurrences of each value. In the example it would give

1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase
-> Stop because 2 was found an even number of times.

This would solve the first extreme example with a complexity of O(mn), which evaluates to O(n).

There's better: if the number of different values is O(1), we could count value appearances inside a hash map, go through them after reading the whole array and return the one that appears an even number of times. This woud still be considered O(1) memory.

The second extreme case would consist in finding the only repeated value inside an array. This seems impossible in O(n), but there are special cases where we can: if the array has n elements and values inside are {1, n-1} + repeated value (or some variant like all numbers between x and y). In this case, we sum all the values, substract n(n-1)/2 from the sum, and retrieve the repeated value.

Solving the second extreme case with random values inside the array, or the general case where m is not constant on n, in constant memory and O(n) time seems impossible to me.

Extra note: here, XORing doesn't work because the number we want appears an even number of times and others appear an odd number of times. If the problem was "give the number that appears an odd number of times, all other numbers appear an even number of times" we could XOR all the values and find the odd one at the end.

We could try to look for a method using this logic: we would need something like a function, that applied an odd number of times on a number would yield 0, and an even number of times would be identity. Don't think this is possible.