Every element appears twice except one. Find it in O(n) time O(1) space.
XOR cancels pairs: a^a=0, a^0=a.
a^a=0
a^0=a
Input
3 2 2 1
Output
1
5 4 1 2 1 2
4