Single Number
Problem statement
You get a non-empty array of integers in which every value appears exactly twice, except for one value that appears once. Return that single value.
Aim for linear time and constant extra space.
Examples
Example 1
Input: nums = [7, 3, 5, 3, 7]
Output: 5
Explanation: 7 and 3 each appear twice; 5 appears once.
Example 2
Input: nums = [10, -2, 10]
Output: -2
Hints
Approach
XOR everything together. XOR has three properties that do all the work: x ^ x = 0, x ^ 0 = x, and the order of operations does not matter.
So 7 ^ 3 ^ 5 ^ 3 ^ 7 can be regrouped as (7 ^ 7) ^ (3 ^ 3) ^ 5 = 0 ^ 0 ^ 5 = 5. Every pair cancels to zero and the lone value survives. Negative numbers work too, since XOR operates on the raw bits.
One pass, one variable.
O(n)Space O(1)class Solution: def singleNumber(self, nums: list[int]) -> int: result = 0 for x in nums: result ^= x # pairs cancel to 0 return resultFollow-up questions
- Exactly two values appear once and the rest appear twice. Find both. (XOR all to get
a ^ b, then split the numbers by any bit that is set in it.) - Every value appears three times except one. Find it in constant space.
Frequently asked questions
No. Three copies XOR to the value itself, not zero. That variant needs per-bit counting modulo 3, or a pair of bitmasks that track counts of one and two.
XOR parity is what RAID 5 uses to rebuild a lost disk: the parity block is the XOR of the data blocks, so XORing the survivors with the parity gives back the missing one. It is the same cancellation idea as this problem. Checksums and simple diffing of bitmaps rely on it too.