Friday, November 9, 2012

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

No comments:

Post a Comment

UA-36403895-1