Two non-repeating numbers in an unsorted array

Design an algorithm to find two non-repeating numbers in an array where other numbers are repeated.
for eg.
input array: {2, 8, 6, 8, 3, 9, 2, 9}
result: 3,6

Approach:-

XOR all the numbers. This gives a value x. 

2^2, 8^8, and 9^9 all become 0. So the remaining is 6^3.

0110

0011

------

0101

------

So x in this case is 5. Take the last set bit, in this case is 1 (that is the unit place). So in the result, one number has 1 in position 1 and the other number has 0 in position 1. That is the reason we have 1 in the result.

Next scan the input array again, but as the numbers are inspected check if the number has 0 or 1 in the position 1. Make 2 XOR groups - one group of numbers with 1 in position 1 and the other group having 0.

The result is the 2 numbers.

Solution