Single Number

Problem

Given 2 * n + 1 numbers, every numbers occurs twice except one, find it.

Example

Given [1, 2, 2, 1, 3, 4, 3], return 4

Challenge

One-pass, constant extra space.

Solution

Two same number can cancel each other by XOR, e.g. 9 ^ 9 = 0, since there's only one number that occurs once, all the other numbers occur twice, we can take XOR of the whole array, whatever left is the number we are looking for.