Single Number

Every element of nums appears twice except one, which appears once. Find it using O(1) extra space.

Examples

Input:  nums = [2, 2, 1]
Output: 1

Input:  nums = [4, 1, 2, 1, 2]
Output: 4

Constraints

• 1 ≤ nums.length ≤ 3 × 10⁴ (odd), values in [−3 × 10⁴, 3 × 10⁴]

Explanation

Hash set

Add a number on first sight, remove it on second; the survivor is the answer. O(n) space.

XOR

XOR has exactly the properties needed:

• a ^ a = 0 (a pair cancels),
• a ^ 0 = a,
• it’s commutative and associative (order doesn’t matter).

So XOR-ing everything together cancels every pair and leaves the single number. It works for negative numbers too, since XOR acts on the bit patterns.

Complexity

• Time: O(n). Space: O(1).