Find nonrepeated 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 nonrepeated number will remain.
Two nonrepeated numbers
If there were 2 nonrepeated numbers and 2N repeated, then how we can
find them in 2N+2 array?
Solution:
Let the 2 nonrepeated 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 nonrepeated
numbers.
K nonrepeated numbers
If there were 3 nonrepeated 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 nonrepeated 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.
