Single Number Problem

Question

---

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

---

XOR satisfies communicative law and associative law. In other words,
X^X = 0 
0 ^X = X
(A^B)^(A^A^B)=A^B^B=A
Therefore,
If we XOR the element one by one, the result is the element which only appears once. If we assume the array is then A ^ B ^ A ^ B ^ C = (A ^ A) ^ (B ^ B) ^ C = C.
Note: Don't forget the case when there is only one element in the array.

Code

---