Question
Find an O(n) algorithm for finding an integer that occurs only once in a list which has all other integers occurring exactly twice. So, in this list of integers, each integer repeats exactly twice, except one. To find that one, what is the best algorithm?
List: 2 2 7 3 1 7 1.
Answer: 3.
Answer
Just XOR all of them…
a XOR b XOR a XOR c XOR b XOR c ... XOR z
= (a XOR a) XOR (b XOR b) XOR ... XOR z
= 0 XOR 0 XOR ... XOR z
= z
Thanks to F.M.A.R. who sent me this problem.
This is the pdf version of this article.