You are given an array in which two numbers are occurring once and all others occur twice. How do you find those two numbers in linear time? What if t

You are given an array in which two numbers are occurring once and all others occur twice. How do you find those two numbers in linear time? What if there are 'k' numbers which are occurring once and rest twice?

If you have constant storage, build the following Hashmap, by looping through the elements of the list.
Key: Number,
Value: Number of times in the list.
O(N) algorithm.

else:
A = (XOR all inputs)

For n = 0 to (number of bits in input):
B = (XOR of all inputs with the nth lowest bit set)
if (A != B) and (B != 0)
return B, A^B

For sample data: [110, 011, 011, 100]
The first loop does this:
A = 110 ^ 011 ^ 011 ^ 100 = 010
In the second loop, XOR inputs with the rightmost bit set:
B = 011 ^ 011 = 0
No answer yet. Continue second loop, and XOR inputs with the second-rightmost bit set:
B = 110 ^ 011 ^ 011 = 110
Now we have an answer for B that is neither 0 nor A, so we return (B, B^A) = (110, 100), which is the answer.