Find the single non-duplicate number in an array

Problem

Every element in the array appears exactly twice except for one element, which appears once. Find that single element.

Example

[4, 1, 2, 1, 2] -> 4

Constraints

• Every element appears twice except one
• Aim for O(n) time and O(1) space

Approach

XOR all elements: equal pairs cancel to 0, leaving the unique value.