LeetCode 136 · Easy · Bit Manipulation

Single Number

Every value in nums appears exactly twice, except one that appears once. Find that one in linear time and constant extra space.

O(n)time
O(1)space
x ^ x = 0pairs cancel

1–13 integers from 0 to 255 · every value twice except one, in any order

nums

res ^ n 8-bit columns · a column gives 1 only when its two bits differ

Seen an odd number of times res is always the XOR of exactly these

public int singleNumber(int[] nums) { int res = 0; for (int n : nums) { res = n ^ res; // a pair XORs to 0 } return res;}
n
—
res
0
res (bits)
—

Why it works

  1. Brute force counts: a hash map of counts finds the value seen once in O(n) time, but O(n) space. Sorting and scanning pairs is O(n log n).
  2. XOR cancels pairs. x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative, so the order does not matter: every pair cancels to 0 wherever its two copies sit, and only the single value survives.
  3. Bit by bit: each column of res is the parity of the 1s seen in that column. A pair adds two 1s (even) to each of its columns; only the single value leaves odd columns behind. One pass, one integer: O(n) time, O(1) space.
  4. Pitfall: start at 0. 0 is XOR's identity. Starting from nums[0] and looping over all of nums would XOR it in twice and cancel it.
  5. Follow-ups: Single Number II (137, triples) counts each bit mod 3; Single Number III (260, two singles) splits the values by one bit where the two singles differ. Missing Number (268) uses the same cancellation.