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