Single Number

Given a non-empty array where every element appears exactly twice except for one, find that single element — in O(n) time and O(1) extra space.

Example

Input: 4 1 2 1 2 Output: 4

Approach

XOR has two properties that solve this instantly: x ^ x = 0 (a value cancels itself out) and x ^ 0 = x. XOR every number in the array together — every paired value cancels to 0, leaving only the unpaired one. No hash set, no sorting, one pass, no extra memory.

Input format

Line 1: the array, space-separated

Print the single number.