233. Single Number III
In the integer array nums, every value appears exactly twice — except for two different values that each appear exactly once. Return those two lonely values, in increasing order so the answer is unique.
A hash map solves it in one line of thought. The real challenge: do it in linear time and constant extra space, using nothing but XOR.
Example 1:
Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Explanation: 1 and 2 both appear twice; 3 and 5 appear once each. Sorted ascending, the answer is 3 5.
Example 2:
Input: nums = [-1, 0]
Output: [-1, 0]
Explanation: Both values appear exactly once, and -1 < 0.
Constraints:
- 2 ≤ nums.length ≤ 3 * 10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
- Exactly two values appear once; every other value appears exactly twice.
Hints:
XOR of a pair of equal numbers is 0, so XOR-ing the whole array cancels every duplicated value. What is left is a ^ b, the XOR of the two singles — useful, but tangled together.
a ^ b is nonzero because a ≠ b, so it has at least one set bit — a bit position where a and b differ. Pick one (the lowest set bit, x & (-x), is convenient) and split the array into 'bit set' and 'bit clear' groups: a and b land in different groups, and every duplicate pair lands together. XOR each group separately.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 1, 3, 2, 5]
Expected output: [3, 5]