Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Every value appears exactly twice except one. XOR every element together: each duplicated pair cancels to 0 (because x ^ x = 0), leaving only the lonely value (because x ^ 0 = x). That is one pass, O(n) time and O(1) space — no hash map needed.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know x ^ x = 0 and x ^ 0 = x well enough to collapse the array with a single XOR fold instead of reaching for a hash map, and whether you can articulate why the pairs cancel.
Where candidates slip
Defaulting to a frequency hash map (O(n) space) when the XOR insight gives O(1), or seeding the accumulator with arr[0] and then also XORing it in the loop, double-counting it.
How to stand out
State the two XOR identities, explain that order doesn't matter so pairs cancel regardless of position, and deliver the one-line O(1)-space fold.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind the single unpaired elementExtra space allowed?YesNoExplore the full treeCollapse the tree
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 2
Hash Map — Count Frequencies
1Hint 1Explore hintHide hint
Count how many times each value appears using a hash map.
2Hint 2Explore hintHide hint
Scan the map for the entry whose count is 1 — that's the lonely integer.
3Hint 3Explore hintHide hint
Correct and linear time, but it stores up to n/2 + 1 distinct keys: O(n) extra space.
A · Core idea
The most direct reading: tally everything, then look for the value seen only once.
Why it's the natural first idea. 'One element appears once, the rest twice' maps cleanly onto counting. A hash map from value to frequency answers 'how many times did I see this?' in O(1) average, so one pass builds the tally and a second pass finds the count-1 entry.
Where it falls short. It works and runs in linear time, but it allocates a map that can grow to about half the array size — O(n) extra space. The problem hints at constant space, and an interviewer asking this is almost always looking for the XOR trick that needs none.
Why mention it anyway. Stating the counting approach shows you understand the problem and gives you a baseline to improve on. Then you say 'but we can avoid the map entirely' and pivot to XOR. That progression — correct-but-heavy to elegant — is what gets graded.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [1, 2, 2]Hash-map state
see 1
Continue scanning
count[1] = 1
1C · Code with teaching comments
Reference implementation previewpublic int lonelyInteger(int[] arr) { Map<Integer, Integer> count = new HashMap<>(); for (int x : arr) { count.merge(x, 1, Integer::sum); }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Counting solves it but pays O(n) space. The leap is realising you don't need counts at all — you only need pairs to cancel, which XOR does for free.
ComplexityO(n) time, O(n) space — One pass to count plus one pass over the map, both linear. The map can hold roughly half the elements, so O(n) space — the cost XOR avoids.
E · Edge cases and pitfalls3Using O(n) space when the problem wants O(1) — the whole reason XOR is preferred.Explore edge casesHide edge cases
Pitfalls
- Using O(n) space when the problem wants O(1) — the whole reason XOR is preferred.
- Scanning the map for count == 1 but comparing to a string or boxed value incorrectly.
- Assuming insertion order to find the answer instead of checking counts.
Approach 2 of 2 · Optimal
XOR Fold — Pairs Cancel (Optimal)
1Hint 1Explore hintHide hint
Recall two facts: x ^ x = 0 and x ^ 0 = x. What happens if you XOR every element of the array together?
2Hint 2Explore hintHide hint
Each value that appears twice contributes x ^ x = 0, so all pairs vanish. The lonely value, with no twin, is left.
3Hint 3Explore hintHide hint
Start an accumulator at 0 and XOR each element into it. Return the accumulator — that's the answer, in one pass and no extra space.
A · Core idea
Collapse the array with XOR and let the duplicates erase themselves.
The two identities that make it work. XOR has two properties you must have at your fingertips: x ^ x = 0 (a value cancels itself) and x ^ 0 = x (zero is the identity). Together they mean that combining any value with its twin produces 0, and combining the result with anything else leaves that thing unchanged.
Why every pair disappears. XOR is commutative and associative, so you can mentally reorder the array to place each value next to its twin: (a ^ a) ^ (b ^ b) ^ ... ^ lonely. Every parenthesised pair becomes 0, and you are left with 0 ^ 0 ^ ... ^ lonely = lonely. The array order in the actual code does not matter — the same cancellation happens during a straight left-to-right fold.
Why start at 0. The accumulator must begin at the XOR identity, 0, so the first element passes through unchanged (0 ^ arr[0] = arr[0]). Seeding it with arr[0] and then also XORing arr[0] in the loop would cancel the first element with itself, corrupting the result. Start at 0 and fold the whole array.
Why this beats the hash map. No counts, no map, no second pass — one accumulator and one loop. O(n) time like the map, but O(1) space, which is exactly what the constant-space hint is steering you toward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [1, 2, 3, 4, 3, 2, 1]Array state
i=0
0 ^ 1 = 1
4C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
XOR is a cancellation machine: feed it the array and matched values annihilate in pairs, leaving the unmatched one. The accumulator starting at 0 is not arbitrary — 0 is XOR's identity, the only safe seed.
ComplexityO(n) time, O(1) space — A single pass performing one XOR per element — O(n) time. Just one integer accumulator — O(1) space.
E · Edge cases and pitfalls6arr = [7] — 0 ^ 7 = 7. A single element is returned directly.Explore edge casesHide edge cases
Edge cases handled
arr = [7]0 ^ 7 = 7. A single element is returned directly.arr = [0, 0, 5]0 ^ 0 ^ 5 = 5. A lonely non-zero survives even amid zero pairs.arr = [4, 5, 4]4 ^ 5 ^ 4 = 5. Order-independent cancellation: the two 4s cancel wherever they are.
Pitfalls
- Seeding the accumulator with arr[0] and also XORing it in the loop — double-counts and corrupts the result.
- Reaching for a hash map out of habit and missing the O(1)-space XOR.
- Assuming XOR only works if duplicates are adjacent — it doesn't matter, XOR is order-independent.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int lonelyInteger(int[] arr) { int result = 0; // XOR identity for (int x : arr) { result ^= x; // twins cancel, loner survives }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong accumulator seed
XOR's identity is 0. Seeding with arr[0] and then XORing arr[0] again in the loop cancels the first element with itself.
Explore the code comparisonHide the code comparison
Wrong accumulator seed
XOR's identity is 0. Seeding with arr[0] and then XORing arr[0] again in the loop cancels the first element with itself.
Don't write this
int result = arr[0];
for (int x : arr) result ^= x; // arr[0] counted twiceWrite this instead
int result = 0;
for (int x : arr) result ^= x; // every element counted once2Defaulting to a hash map
Counting works but costs O(n) space. The interviewer's constant-space hint points straight at XOR.
Explore the code comparisonHide the code comparison
Defaulting to a hash map
Counting works but costs O(n) space. The interviewer's constant-space hint points straight at XOR.
Don't write this
from collections import Counter
return next(v for v, c in Counter(arr).items() if c == 1) # O(n) spaceWrite this instead
result = 0
for x in arr:
result ^= x
return result # O(1) space3Assuming pairs must be adjacent
XOR is commutative and associative, so duplicates cancel no matter where they appear — sorting is unnecessary.
Explore the code comparisonHide the code comparison
Assuming pairs must be adjacent
XOR is commutative and associative, so duplicates cancel no matter where they appear — sorting is unnecessary.
Don't write this
arr.sort() # needless O(n log n); XOR doesn't need orderWrite this instead
result = 0
for x in arr:
result ^= xRevise
Carry the pattern into the interview
Pattern to remember
XOR the whole array; pairs cancel, the loner survives
Code pattern to memorize
result = 0
for x in arr:
result ^= x
return resultRules to remember
- 1x ^ x == 0 — any value XORed with itself vanishes. This is what makes every duplicate pair disappear.
- 2x ^ 0 == x — XOR with zero is the identity, so start the accumulator at 0 and the loner passes through untouched.
- 3XOR is commutative and associative, so order does not matter — you can fold the array left to right in one pass.
- 4Start the accumulator at 0, never at
arr[0]unless you then skip index 0 — double-counting the first element flips the answer. - 5This beats counting in a hash map (O(n) space) and sorting (O(n log n)) — XOR is O(n) time, O(1) space.
Use this pattern when
- Find the single unpaired element where all others pair up
- Detect a missing or extra value via cancellation
- You want O(1) space, not a frequency map
- Pairs (or even counts) cancel and you need the odd one out
Choose another pattern when
- Some value appears three times, not twice → XOR alone won't isolate it (use bit-count mod 3)
- Two distinct singletons exist → one XOR mixes them; split by a differing bit
- You need the count of each element, not just the loner → use a hash map
- Elements are not integers / not XOR-able → fall back to hashing
Interview takeaway
XOR is the cancellation operator: identical values annihilate, leaving the odd one standing. Lonely Integer is the cleanest use — fold the array with ^ and the answer falls out in O(1) space. The same trick powers Missing Number and Single Number II/III.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternXOR cancellation. When duplicates pair up and you need the odd one out, XOR the whole collection: identical values annihilate (x ^ x = 0) and the identity (x ^ 0 = x) preserves the survivor. Recurs in Missing Number, Single Number II/III, and finding a swapped pair.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Missing NumberXOR indices with values; the unmatched index is the missing number.
- Single Number IIComing soonEvery element appears three times except one — count bits mod 3 instead of XOR.
- Single Number IIIComing soonTwo lonely elements — XOR everything, then split the array by a set bit of the result.