easy
Single Number
In a non-empty integer array every element appears exactly twice except one, which appears once. Find that element in linear time using constant extra memory.
Constraints
- 1 ≤ n ≤ 3 · 10^4
- -3 · 10^4 ≤ nums[i] ≤ 3 · 10^4
- Exactly one element appears once
Examples
in: nums = [4,1,2,1,2]
out: 4
Recognition clues
- Pairs cancel — a ⊕ a = 0
- XOR is commutative, so order does not matter
- Constant space forbids a hash map
Pattern
Bit ManipulationXOR cancels pairs, so "every element appears twice except one" is a single XOR pass with no extra memory. Sets of at most ~20 items fit in an integer bitmask, turning subset enumeration and "which nodes have been visited" states into cheap arithmetic that DP and BFS can index directly.
Solution
XOR all elements together. Every value appearing twice contributes a ⊕ a = 0, and XOR with 0 is the identity, so the accumulated result is exactly the value that appears once. No extra memory is required.
time O(n)space O(1)
Alternative approaches
- A hash set or sorting works but uses O(n) space or O(n log n) time. For "every element appears three times" count each bit modulo 3.
Code it yourself
Solve in
Hints: