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;

This partition segregates the numbers such that all the pairs with ith bit 1 goes to one partition and all pairs with ith bit 0. But x and y fall into two different buckets their bit patterns will be different.

Now finding the XOR value of these partitions separately gives us the required result.

In the above example. The XOR value has 1st bit as 1.
{2,2,3} forms one partition and {1,1,4,4,5} forms another partition.

Parition-1    Partion-2
0010          0001
0011          0100
0010          0001
                 0100
                 0101
———————
0011(3)    0101(5)

So 3,5 are the answers

Here is the Java code to do this.

Leave a Reply Cancel reply