Find non-repeated number in a 2N+1
array where all N elements are repeated
Solution:
A number XORed with itself gives 0
So,
if we XOR all numbers, all repeated numbers will cancel each other.
But
the non-repeated number will remain.
Two non-repeated numbers
If there were 2 non-repeated numbers and 2N repeated, then how we can
find them in 2N+2 array?
Solution:
Let the 2 non-repeated numbers be P and Q and let the XOR of all
elements be X.
Then
X would have only those bits set where only P or Q have a bit set but
not both.
If
we take one of the set bit’s position in X and divide the array
in 2 parts such that one part contains numbers with that bit set and
one part does not contain that bit set, then P and Q would come in
different groups but repeated numbers would go in pairs to each
group.
Then
we can XOR each group individually to find the 2 non-repeated
numbers.
K non-repeated numbers
If there were 3 non-repeated numbers P, Q and R, then we cannot use the above technique because
its possible that those three numbers XOR to zero giving a false impression of being repeated numbers.
Example: 1, 2 and 3 - these three numbers are non-repeated but they XOR to zero.
Corollary
The XOR technique can be used to find a number occurring odd number of times in
an array where other numbers occur even number of times.
|