Bit Manipulation : Find 2 numbers which are repeated odd number of times in an array in which all other numbers are repeated even number of times

Today I would be sharing a problem which can be very efficiently solved using bit manipulations.

Problem :

Given an array containing integer numbers containing numbers which are repeated even number of times except two numbers which are repeated odd number of times. The range of integer numbers is not given. Find the two numbers which are repeated even odd number of time.

Solution :

It can be solved in O(n) time and O(1) space. The basic concept here is x ^ x = 0. Here's the algorithm :

1) XOR all the elements in the array. This would nullify all the elements which are repeated even number of times. So, we would get the XOR of elements which are repeated odd number of times.

2) Now divide the set of numbers into 2 sets such that numbers which are repeated odd number of times go into different sets. To divide the set in this way is quite easy given that the set bits in the XOR of two numbers are the bits in which the two numbers differ. From step 1, we got the XOR of the numbers which are repeated odd number of times. Divide all the elements of the array into 2 sets depending on any of the set bits in the XOR output of step 1.

3) XOR all the elements within each set and we would get the elements which are repeated odd number of times since the elements which are repeated even number of times would have nullified  each other.

Here is the code snippet :

Now result1 and result2 would hold the numbers which are repeated odd number of times.

There is a trick to find the lowest bit position set. Suppose x is a number and we wish to find the lowest bit position which is set. We can do so by :
x |= x & (x-1);
The above code snippet can be made more efficient by employing the above rule.