Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
XOR all the numbers together; paired values cancel to 0, and the result is the single number. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you apply XOR cancellation for the O(1)-space solution.
Where candidates slip
Defaulting to a HashSet or sort.
How to stand out
State the XOR properties and extend to Single Number II/III variants.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
XOR fold
1Hint 1Explore hintHide hint
What happens when you XOR a value with itself?
2Hint 2Explore hintHide hint
Fold the array with XOR — what's left?
3Hint 3Explore hintHide hint
Can you avoid the O(n) space of a hash set?
A · Core idea
Every element appears twice except one. XOR the whole array: paired values cancel (x ^ x = 0), leaving the unique element. O(n) time, O(1) space — the textbook solution.
Why XOR isolates the loner. XOR is commutative and associative, so you can reorder the fold freely; each duplicated pair XORs to 0, and 0 ^ (unique) = unique. The order of elements is irrelevant.
Why it beats the hash-set approach. A set/map that adds-and-removes seen values also finds the single number but uses O(n) extra space. The XOR fold uses one accumulator — O(1). Sorting then scanning pairs is O(n log n). XOR wins on both axes.
The interviewer is specifically checking whether you reach for XOR-cancellation rather than a HashSet.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2, 3, 2]0 ^ 2
23C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The interviewer is checking whether you know the XOR-cancellation property rather than reaching for a HashSet.
ComplexityO(n) time, O(1) space — one XOR per element, single accumulator → O(n) time, O(1) space.
E · Edge cases and pitfalls4nums = [1, 1, 4] — 1s cancel → 4.Explore edge casesHide edge cases
Edge cases handled
nums = [1, 1, 4]1s cancel → 4.nums = [9]Single element → 9.
Pitfalls
- Using O(n) extra space with a hash set.
- Sorting first (O(n log n)) when XOR is O(n)/O(1).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int singleNumber(int[] nums) { int x = 0; for (int v : nums) x ^= v; return x; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
- Using O(n) extra space with a hash set.
- Sorting first (O(n log n)) when XOR is O(n)/O(1).
Revise
Carry the pattern into the interview
Pattern to remember
XOR cancellation
Code pattern to memorize
x = 0; for v: x ^= v; return xRules to remember
- 1x ^ x = 0.
- 2XOR all elements.
- 3Survivor = the single one.
Use this pattern when
- Unpaired element
- XOR cancellation
Choose another pattern when
- Element appears 3× — XOR alone won't isolate it
Interview takeaway
XOR the array to find the lone unpaired number in O(1) space.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: XOR cancellation. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Single NumberComing soonLeetCode 136 — same XOR fold.
- Odd-Occurring NumberGeneralises to odd counts.