Learning Outcome
After this lesson, you should be able to split numbers into two XOR groups using a bit where the two answers differ.
Problem Statement
Given an integer array where exactly two elements appear once and all others appear twice, return the two single elements.
| Input | Output | Why |
|---|---|---|
nums = [1,2,1,3,2,5] | [3,5] | 1 and 2 cancel as pairs; 3 and 5 remain as the two unique values. |
Brute Force Approach
Use a frequency map and collect values with count 1. This is simple but uses extra memory.
Optimized Approach
XOR all values to get xorAll = a xor b. Pick the rightmost set bit of xorAll to separate a and b into different groups, then XOR within each group.
Exact Pseudocode
xorAll = 0
for x in nums:
xorAll = xorAll xor x
mask = xorAll & -xorAll
a = 0
b = 0
for x in nums:
if x & mask:
a = a xor x
else:
b = b xor x
return [a, b]Reference Code
class Solution:
def singleNumber(self, nums):
xor_all = 0
for x in nums:
xor_all ^= x
mask = xor_all & -xor_all
a = 0
b = 0
for x in nums:
if x & mask:
a ^= x
else:
b ^= x
return [a, b]Sample Dry Run
| Step | State | Result |
|---|---|---|
| XOR all | duplicates cancel | xorAll = 3 xor 5 |
| Find mask | mask is a bit where 3 and 5 differ | groups separate answers |
| XOR group A | duplicates inside group cancel | one answer remains |
| XOR group B | duplicates inside group cancel | other answer remains |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | The array is scanned twice. |
| Space | O(1) | Only xorAll, mask, and two answers are stored. |
Edge Cases
- The two unique values must be different, so xorAll is nonzero.
- Output order usually does not matter.
- Use a real differing bit, not a random bit.
Interview Checklist
- XOR all values first.
- Use rightmost set bit to split groups.
- XOR inside each group to cancel duplicates.
FAQs
Why does the mask separate the two answers?
The mask is set in xorAll, so one answer has that bit and the other does not.
Why do duplicates stay together?
Equal numbers have the same mask bit, so each duplicate pair lands in the same group and cancels.
What is the core pattern?
XOR partition by rightmost set bit.