How to find a 2 unpaired elements in array?

Question

You have an array with n=2k+2 elements where 2 elements haven't pair. Example for 8 elemets array: 1 2 3 47 3 1 2 0. "47" and "0" haven't pair in array. If I have array where only 1 element has't pair, I solve this problem with XOR. But I have 2 unpair elements! What can I do? Solution could be for a O(n) time performance and for O(1) additional memory.

Answer 1

Some hints...

It will take 2 passes. First, go through the list and XOR all elements together. See what you get. Proceed from there.

Edit: The key observation about the result of the first pass should be that it shows you the set of bits in which the 2 unpaired elements differ.

Answer 2

Use INT_MAX/8 bytes of memory. Walk the array. XOR the bit corresponding to each value with 1. If there are 0 or 2 instances the bit will end up 0. If there is only one instance, it will be set. O(1) mem, O(N) time.