Given an integer array nums, exactly two elements appear only once and every other element appears exactly twice. Find and return the two elements that appear only once. You may return the answer in any order.
Your solution must run in linear time and use only constant extra space.
x ^ x = 0), so only the two unpaired values survive, combined as a ^ b.a ^ b works — each marks a position where the two loners disagree. The lowest one, x & (-x), is the simplest to grab.x & (-x) isolating the lowest set bit is the same operation a Fenwick (binary indexed) tree uses to walk its ranges.Input: nums = [1, 2, 1, 3, 2, 5] Output: [3, 5] 1 and 2 each appear twice and cancel; 3 and 5 are the two singles. [5, 3] is also accepted.
Input: nums = [-1, 0] Output: [-1, 0] Both values appear once; there are no pairs to cancel.
Input: nums = [0, 1] Output: [0, 1] Two elements, each appearing once.
- 2 <= nums.length <= 3 * 10^4 - -2^31 <= nums[i] <= 2^31 - 1 - Exactly two elements appear only once and all the other elements appear exactly twice.
In Single Number, one loner survived when you XORed everything — the pairs cancelled and left it standing. Here there are two loners, so XORing the whole array leaves you with a ^ b, their combined fingerprint. The trick is to split the array into two halves so each loner ends up alone in its own group — and one shared bit is all you need to do the split.
x ^ x = 0, so XORing the whole array collapses every pair and leaves a ^ b.x & (-x) extracts the lowest set bit — the tool that picks a splitting bit.0 or 1.“Exactly two elements appear once, the rest exactly twice?”
Yes, so there are always precisely two answers to return.
“Does the output order matter?”
No — any order is accepted, since the two loners are interchangeable.
“Can the values be negative?”
Yes, across the 32-bit signed range — XOR and the bit split handle them unchanged.
“What space am I allowed?”
Constant, which rules out a frequency map and points to the XOR-and-split idea.
If I XOR everything, the pairs vanish and I'm left with a ^ b — the XOR of the two loners.
Since a and b differ, that result has at least one set bit; I'll grab the lowest one.
That bit is 1 in one loner and 0 in the other, so partitioning on it separates them — then I XOR each group.
Worked example — nums = [1, 2, 1, 3, 2, 5]
XOR of all = 3 ^ 5 = 6 (0110) -- the pairs 1,1 and 2,2 cancelled
lowest set bit = 6 & -6 = 2 (0010)
bucket bit=1: {2,2,3} -> XOR = 3
bucket bit=0: {1,1,5} -> XOR = 5
answer: [3, 5]
Every paired value cancels itself, so one sweep of XOR reduces the whole array to a ^ b. Since a != b, this is non-zero — it has at least one set bit.
Any set bit of a ^ b is a position where a and b disagree. Grouping numbers by that bit puts a in one group and b in the other. Take the lowest set bit with x & (-x) — any differing bit works.
Two copies of the same value share every bit, so they always land in the same group and cancel there. Each group therefore reduces — under XOR — to exactly its single loner.
| Hash set | XOR + split | |
|---|---|---|
| Idea | Toggle membership; the two survivors are the answer | XOR all, split on a differing bit, XOR each half |
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
Both are linear; only the XOR approach hits constant space. Full code is in the Approaches selector below.
Key takeaway
Two loners among pairs? XOR everything to get a ^ b, isolate one differing bit with x & (-x), partition the array on that bit, and XOR each half to recover the two answers. The move that unlocks it: a single differing bit cleanly separates the two singles while keeping every pair intact.
xor_all = XOR of every element # = a ^ b diff = xor_all AND (-xor_all) # a bit where a and b differ a = XOR of elements with that bit set b = xor_all XOR a return [a, b]