Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 6

x = 0

Every value appears twice except one. Fold XOR: a⊕a=0, a⊕0=a.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Single Number

Every element appears twice except one. Find the single one.

a⊕a=0, a⊕0=a; fold XOR cancels pairs.

Unverified

Time O(n)Space O(1)

Idea. x = 0; for v in nums: x ^= v.

Walkthrough. [4,1,2,1,2] → 4.

Trade-offs. O(1) space vs hash set O(n).

Solution

export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}

export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}

Bit XOR identity.

XOR is associative. a ^ a = 0 and a ^ 0 = a. Pairs cancel and the single number remains.
Order does not matter. One element is itself. 0 is the identity.
Two numbers that appear once would leave their XOR mixed. This problem promises exactly one.