136. Single Number

Every element of a non-empty array appears twice except for one. Find that single one in linear time and constant extra space.

x ^ x = 0 and x ^ 0 = x, and XOR is order-independent. XOR all numbers: every pair cancels, leaving the single number.

1function singleNumber(nums: number[]): number {
2  let acc = 0;
3  for (const x of nums) acc ^= x;
4  return acc;
5}