The problem
In a non-empty array of integers, every value appears twice except one, which appears once. Find it, in linear time and constant extra space.
Examples
01
- Input
nums = [2, 2, 1]
- Output
1
02
- Input
nums = [4, 1, 2, 1, 2]
- Output
4
03
- Input
nums = [1]
- Output
1
Constraints
- 1 ≤ nums.length ≤ 3 × 10⁴
- −3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
- Exactly one value appears once; every other appears twice.
The idea
XOR (written ^) compares two numbers bit by bit: a bit of the result is 1 where the two bits differ. So x ^ x = 0 (every bit matches itself), x ^ 0 = x, and the order of XORs does not matter.
XOR everything together. Each value that appears twice meets its twin and cancels to 0, wherever they are in the array; what remains is the single one. For [4, 1, 2, 1, 2]: 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def singleNumber(self, nums: List[int]) -> int: # x ^ x = 0 and x ^ 0 = x, and ^ ignores order: every pair cancels, the loner is left. out = 0 for x in nums: out ^= x return out