136. Single Number
You receive an array of integers nums in which every value appears exactly twice, apart from a single value that appears only once. Return the value that has no partner.
A follow-up worth chasing: can you find it in one pass, using no memory beyond a couple of variables?
Example 1:
Input: nums = [5, 5, 9]
Output: 9
Explanation: The two 5s pair up, leaving 9 as the lone value.
Example 2:
Input: nums = [6, 3, 8, 3, 8]
Output: 6
Explanation: 3 and 8 each appear twice; 6 appears once.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- nums.length is odd
- -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴
- Every value appears exactly twice, except one value that appears exactly once.
Hints:
A hash map of value → count solves it in one pass, at the cost of O(n) extra space. Get that working first.
Sorting puts equal values side by side — then the loner is the value whose neighbor doesn't match. O(n log n), no hash map.
XOR cancels pairs: x ^ x = 0, x ^ 0 = x, and order doesn't matter. XOR the whole array together and see what survives.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 5, 9]
Expected output: 9