Problem solving with programming: Finding two numbers occuring once

Problem solving with programming: Finding two numbers occuring once

Given an array containing all elements twice except two numbers. Write a program to find those two numbers.

For example let us consider the following array

{2, 3, 2, 1, 4, 1, 4, 5} 
The answer is {3,5} because they appear only once and all remaining elements appear twice.

This question is somewhat similar to earlier post. This gives us a hint to use XOR operation to solve this problem. Let us see how we can utilize XOR operation.

We first find the XOR of all the elements in the array. This gives a bit pattern which is an XOR of required two values because all other elements occurs twice they get zeroed out.

For the above example the xor value is 0110 = 0011 ^ 0101

Let the two unique numbers are x, y. The next problem is how to find x,y from this xor value. Let us denote ith bit is the first set bit in the xor result. We divide all the numbers in the array into two parts. One part containing all the numbers with bit i = 1, and the other part containing all the numbers with bit i = 0;

Read full article from Problem solving with programming: Finding two numbers occuring once