Given an array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Use a trick of bitwise operation XOR: 0^n = n . n is an integer. So here use zero to XOR each element. If there are even number of the element, result will be back to zero and ready to be XOR with the next element. If there are odd number of the element, result will be the element itself. Furthermore, XOR is commutative. So the order in the array doesn’t matter.