Make delicious recipes!

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.





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal