Loading…

easyBit ManipulationLC #136Frequently asked

Single Number

Q: How do you solve Single Number using the Hash Set — Add and Remove approach?

When to use it: Mention it as the obvious correct-but-not-optimal baseline, then say 'but this uses O(n) space, and the prompt wants O(1)'. Keep a set. For each number, if it's already in the set remove it, otherwise add it. A value that appears twice gets added then removed, leaving the set; the lone value is added once and never removed, so it's the only survivor. **Why this is the instinctive first answer.** 'Appears twice except one' maps directly to 'cancel things that pair up', and a set is the most literal way to pair them: presence means 'seen an odd number of times so far'. After the full pass, the only value still marked present is the one with no partner. **Why it doesn't meet the bar.** The set can grow to half the array before the duplicates start arriving, so this is O(n) extra space. The prompt explicitly demands O(1). Stating this approach shows you can solve it, then pivoting to XOR shows you can solve it *well*. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Single Number using the XOR All Elements (Optimal) approach?

When to use it: The answer they want. Frame it as 'XOR cancels pairs because a ^ a = 0, so the single survivor falls out for free'. Initialise an accumulator to `0` and XOR every element into it. Because each duplicated value appears an even number of times, all duplicates cancel to `0`, and the lone value XOR-ed against `0` is itself. **Why `a ^ a = 0`.** XOR returns 1 in a bit position only when the two bits differ. A number XOR-ed with itself has identical bits everywhere, so every position is `0` — the value annihilates itself. That is the whole engine of this solution: any value appearing twice contributes nothing to the final result. **Why order doesn't matter.** XOR is commutative (`a ^ b = b ^ a`) and associative (`(a ^ b) ^ c = a ^ (b ^ c)`). So even though the duplicates are scattered through the array, the algebra lets you mentally reorder them into pairs — `4 ^ (1 ^ 1) ^ (2 ^ 2)` — and every pair collapses to `0`, leaving `4 ^ 0 ^ 0 = 4`. **Why seed with `0`.** Zero is XOR's identity (`0 ^ x = x`), so starting the fold at `0` doesn't disturb anything — the accumulator simply becomes whatever survives the cancellations. This is also why a single-element array works: `0 ^ x = x`. Time complexity: O(n). Space complexity: O(1).

LCPractice

Bit Manipulation · 1 of 20 · 6 min

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with linear runtime complexity and use only constant extra space.

In plain English

Find the one value that has no partner. Every other value shows up an even number of times (exactly twice), so they can all be paired off and discarded. The challenge isn't correctness — a hash set solves that — it's doing it without extra space.

Examples

Example 1

Input: nums = [2, 2, 1]
Output: 1
Note: 2 ^ 2 = 0, then 0 ^ 1 = 1. The pair of 2s cancels, leaving 1.

Example 2

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Note: XOR everything: the two 1s cancel, the two 2s cancel, 4 is left standing.

Example 3

Input: nums = [1]
Output: 1
Note: A single element with no partner — 0 ^ 1 = 1.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
Each element appears exactly twice except one element which appears once
Required: O(n) time and O(1) extra space

Clarifying questions4First question: Is it guaranteed that exactly one element appears once and all others exactly twice?Explore questions

Q1.Is it guaranteed that exactly one element appears once and all others exactly twice?
Yes. That guarantee is what lets XOR cancel every pair cleanly. If some appeared three times, XOR would break.
Q2.Can the numbers be negative?
Yes. XOR operates on the two's-complement bit pattern, so negatives cancel exactly the same as positives.
Q3.Is the array sorted?
No, and it doesn't matter — XOR is commutative, so the result is independent of order.
Q4.Are the O(n) time and O(1) space requirements hard constraints?
Yes. That rules out sorting (O(n log n)) and a hash set (O(n) space) as the intended answer, even though both are correct.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Every element appears twice except one. XOR all the numbers together: identical values cancel (a ^ a = 0) and XOR-with-zero is identity (a ^ 0 = a), so the survivor is the unique element. O(n) time, O(1) space — beats the hash-map/sort answers the interviewer expects you to outgrow.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know XOR's algebraic properties well enough to turn a counting problem into a single O(1)-space pass — or whether you stop at the hash-set answer that any beginner reaches.

Where candidates slip

Solving it with a hash set or sorting (correct but O(n) space / O(n log n) time), and not recognising that the 'appears twice' guarantee is exactly what makes XOR cancel.

How to stand out

State `a ^ a = 0` and `a ^ 0 = a` out loud, note that XOR is commutative so order is irrelevant, and mention this generalises to Missing Number and Single Number III.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Add and Remove	`O(n)`	`O(n)`	Mention it as the obvious correct-but-not-optimal baseline, then say 'but this uses O(n) space, and the prompt wants O(1)'.	Read
2	XOR All Elements (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'XOR cancels pairs because a ^ a = 0, so the single survivor falls out for free'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewEvery element twice except oneO(1) space required?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Add and Remove

TimeO(n)SpaceO(n)

Mention it as the obvious correct-but-not-optimal baseline, then say 'but this uses O(n) space, and the prompt wants O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you tracked which numbers you've already seen, the unique one is the only value that never gets a second visit.

2Hint 2Explore hint

Use a set: add a number the first time you see it, remove it the second time. What's left at the end?

3Hint 3Explore hint

After processing every element, the set contains exactly one value — the single number. Pairs added then removed cancel out.

A · Core idea

Keep a set. For each number, if it's already in the set remove it, otherwise add it. A value that appears twice gets added then removed, leaving the set; the lone value is added once and never removed, so it's the only survivor.

Why this is the instinctive first answer. 'Appears twice except one' maps directly to 'cancel things that pair up', and a set is the most literal way to pair them: presence means 'seen an odd number of times so far'. After the full pass, the only value still marked present is the one with no partner.

Why it doesn't meet the bar. The set can grow to half the array before the duplicates start arriving, so this is O(n) extra space. The prompt explicitly demands O(1). Stating this approach shows you can solve it, then pivoting to XOR shows you can solve it well.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 1, 2, 1, 2]

x=4

not in set → add

Stateset = {4}

Final result4

C · Code with teaching comments

Reference implementation previewpublic int singleNumber(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int x : nums) { if (!seen.add(x)) { seen.remove(x);Explore the full code

solution.javaJava

Hash Set — Add and Remove — reference

3 teaching notes

1
public int singleNumber(int[] nums) {
2
    Set<Integer> seen = new HashSet<>();
3
    for (int x : nums) {
4
        // add returns false if x was already present — meaning this is its second
5
        // appearance.
6
        if (!seen.add(x)) {
7
            // Second sighting cancels the first: remove it so only unpaired values
8
            // remain.
9
            seen.remove(x);
10
        }
11
    }
12
    // Exactly one value is left — the single number.
13
    return seen.iterator().next();
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

A set used this way is really a parity tracker: 'is this value present an odd number of times?'. That parity idea is exactly what XOR computes bit-by-bit for free — which is the bridge to the optimal solution.

ComplexityO(n) time, O(n) space — One pass with O(1) average set operations is O(n) time; the set can hold up to n/2 + 1 distinct values, so O(n) space.

E · Edge cases and pitfalls5nums = [1] — 1 is added once and never removed; set = {1} → returns 1.Explore edge cases

Edge cases handled

nums = [1]1 is added once and never removed; set = {1} → returns 1.
nums = [-1, -1, 5]-1 added then removed, 5 added once → returns 5. Negatives are fine in a set.

Pitfalls

Using a frequency map instead of a presence set — same complexity but more code and the same O(n) space cost.
Forgetting the prompt's O(1)-space requirement and presenting this as the final answer.
Assuming the set is non-empty at the end without relying on the 'exactly one single' guarantee.

03.2

Approach 2 of 2 · Optimal

XOR All Elements (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'XOR cancels pairs because a ^ a = 0, so the single survivor falls out for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Is there a single arithmetic/bitwise operation where combining a value with itself produces nothing, so duplicates erase each other?

2Hint 2Explore hint

XOR has two key laws: x ^ x = 0 and x ^ 0 = x. What happens if you XOR every element of the array into one running total?

3Hint 3Explore hint

Fold the whole array with XOR starting from 0. Every value that appears twice contributes x ^ x = 0; the lone value contributes itself.

A · Core idea

Initialise an accumulator to 0 and XOR every element into it. Because each duplicated value appears an even number of times, all duplicates cancel to 0, and the lone value XOR-ed against 0 is itself.

Why `a ^ a = 0`. XOR returns 1 in a bit position only when the two bits differ. A number XOR-ed with itself has identical bits everywhere, so every position is 0 — the value annihilates itself. That is the whole engine of this solution: any value appearing twice contributes nothing to the final result.

Why order doesn't matter. XOR is commutative (a ^ b = b ^ a) and associative ((a ^ b) ^ c = a ^ (b ^ c)). So even though the duplicates are scattered through the array, the algebra lets you mentally reorder them into pairs — 4 ^ (1 ^ 1) ^ (2 ^ 2) — and every pair collapses to 0, leaving 4 ^ 0 ^ 0 = 4.

Why seed with `0`. Zero is XOR's identity (0 ^ x = x), so starting the fold at 0 doesn't disturb anything — the accumulator simply becomes whatever survives the cancellations. This is also why a single-element array works: 0 ^ x = x.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 1, 2, 1, 2]

Array state

x=4

acc: 0 ^ 4 = 4

x ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

XOR All Elements (Optimal) — optimal

3 teaching notes

1
public int singleNumber(int[] nums) {
2
    // Seed with XOR's identity: 0 ^ x = x, so it starts neutral.
3
    int result = 0;
4
    for (int x : nums) {
5
        // Fold each element in. Pairs cancel (a ^ a = 0); the lone value survives.
6
        result ^= x;
7
    }
8
    // After all cancellations, only the single number's bits remain.
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Reframe the array as a parity question per bit: each bit of the answer is 1 exactly when an odd number of inputs have that bit set. The duplicated values flip every bit an even number of times (back to where it started), so only the unique value's bits remain. XOR computes all 32 of those parities simultaneously in one machine instruction.

ComplexityO(n) time, O(1) space — A single pass doing one constant-time XOR per element is O(n) time; only one integer accumulator is kept, so O(1) space.

E · Edge cases and pitfalls5nums = [1] — 0 ^ 1 = 1. The identity seed makes single-element arrays just work.Explore edge cases

Edge cases handled

nums = [1]0 ^ 1 = 1. The identity seed makes single-element arrays just work.
nums = [-2, -2, 3]XOR on two's-complement bits: -2 ^ -2 = 0, then 0 ^ 3 = 3. Negatives cancel identically.

Pitfalls

Seeding the accumulator with nums[0] and looping from index 1 — works, but seeding 0 and looping all is cleaner and avoids an empty-array crash.
Trying to extend this to 'each appears three times' — XOR only cancels even counts; that variant needs per-bit counting mod 3.
Confusing XOR (^) with OR (|) or AND (&) — only XOR has the self-cancelling property.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int singleNumber(int[] nums) { int result = 0; for (int x : nums) { result ^= x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using a hash set as the final answer

It's O(n) space, but the prompt explicitly demands O(1). It signals you don't know XOR's cancellation property.

Explore the code comparison

Don't write this

seen = set()
for x in nums:
    if x in seen:
        seen.remove(x)
    else:
        seen.add(x)
return seen.pop()

Write this instead

result = 0
for x in nums:
    result ^= x
return result

Using OR instead of XOR

OR accumulates bits but never clears them, so duplicates don't cancel — you get the bitwise-OR of all values, not the single one.

Explore the code comparison

Don't write this

int result = 0;
for (int x : nums) {
    result |= x;   // OR never cancels pairs
}
return result;

Write this instead

int result = 0;
for (int x : nums) {
    result ^= x;   // XOR cancels every pair
}
return result;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

XOR cancellation (pair annihilation)

Code pattern to memorize

result = 0
for x in nums:
    result ^= x   # pairs cancel to 0, single survives
return result

Rules to remember

1Seed the accumulator at 0, the XOR identity: 0 ^ x = x.
2The two laws that make this work: a ^ a = 0 (self-cancel) and a ^ 0 = a (identity).
3XOR is commutative and associative, so order doesn't matter — every duplicate finds its partner no matter where it sits.
4This needs O(1) space — if you reach for a hash set you've solved it, but not optimally.
5XOR only cancels things that appear an even number of times. The 'twice' guarantee is load-bearing.

Use this pattern when

Every element repeats an even number of times except one
You need O(1) space and the values fit in a fixed-width int
Phrasing like 'find the element that appears once / an odd number of times'
You can stream the input — one pass, no storage

Choose another pattern when

Elements repeat three times except one → XOR cancels pairs, not triples (Single Number II needs bit counting)
Two unique elements instead of one → XOR gives a^b combined, needs a split step (Single Number III)
Need the count of how many times each value appears → hash map
Values aren't integers (strings, objects) → XOR doesn't apply

Interview takeaway

XOR is the interview's favourite 'cancel the pairs' tool. The instant you hear 'everything appears twice except one', stop thinking about counting and start thinking about XOR — the same trick reappears in Missing Number, Single Number II/III, and Find the Duplicate.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternXOR Pair-Cancellation. Recognise it whenever values pair off and you want the odd one out in O(1) space. The same a ^ a = 0 lever powers Missing Number, Single Number II/III, and Find the Difference.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Single Number II
Coming soon
Every element appears three times except one. XOR can't cancel triples — count each bit mod 3.
Single Number III
Coming soon
Two unique elements. XOR everything to get a^b, then use a set bit of a^b to split into two groups.
Missing Number
Same XOR-cancellation idea: XOR all indices with all values; the missing number survives.
Find the Difference
Coming soon
XOR every character of both strings; the extra letter is the lone survivor.

Same pattern

Continue · Next problem

Number of 1 Bits

easyBit ManipulationLC #136Frequently asked

Single Number

LCPractice

Bit Manipulation · 1 of 20 · 6 min

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with linear runtime complexity and use only constant extra space.

In plain English

Examples

Example 1

Input: nums = [2, 2, 1]
Output: 1
Note: 2 ^ 2 = 0, then 0 ^ 1 = 1. The pair of 2s cancels, leaving 1.

Example 2

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Note: XOR everything: the two 1s cancel, the two 2s cancel, 4 is left standing.

Example 3

Input: nums = [1]
Output: 1
Note: A single element with no partner — 0 ^ 1 = 1.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
Each element appears exactly twice except one element which appears once
Required: O(n) time and O(1) extra space

Clarifying questions4First question: Is it guaranteed that exactly one element appears once and all others exactly twice?Explore questions

Q1.Is it guaranteed that exactly one element appears once and all others exactly twice?
Yes. That guarantee is what lets XOR cancel every pair cleanly. If some appeared three times, XOR would break.
Q2.Can the numbers be negative?
Yes. XOR operates on the two's-complement bit pattern, so negatives cancel exactly the same as positives.
Q3.Is the array sorted?
No, and it doesn't matter — XOR is commutative, so the result is independent of order.
Q4.Are the O(n) time and O(1) space requirements hard constraints?
Yes. That rules out sorting (O(n log n)) and a hash set (O(n) space) as the intended answer, even though both are correct.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know XOR's algebraic properties well enough to turn a counting problem into a single O(1)-space pass — or whether you stop at the hash-set answer that any beginner reaches.

Where candidates slip

Solving it with a hash set or sorting (correct but O(n) space / O(n log n) time), and not recognising that the 'appears twice' guarantee is exactly what makes XOR cancel.

How to stand out

State `a ^ a = 0` and `a ^ 0 = a` out loud, note that XOR is commutative so order is irrelevant, and mention this generalises to Missing Number and Single Number III.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Add and Remove	`O(n)`	`O(n)`	Mention it as the obvious correct-but-not-optimal baseline, then say 'but this uses O(n) space, and the prompt wants O(1)'.	Read
2	XOR All Elements (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'XOR cancels pairs because a ^ a = 0, so the single survivor falls out for free'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Add and Remove

TimeO(n)SpaceO(n)

Mention it as the obvious correct-but-not-optimal baseline, then say 'but this uses O(n) space, and the prompt wants O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you tracked which numbers you've already seen, the unique one is the only value that never gets a second visit.

2Hint 2Explore hint

Use a set: add a number the first time you see it, remove it the second time. What's left at the end?

3Hint 3Explore hint

After processing every element, the set contains exactly one value — the single number. Pairs added then removed cancel out.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 1, 2, 1, 2]

x=4

not in set → add

Stateset = {4}

Final result4

C · Code with teaching comments

Reference implementation previewpublic int singleNumber(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int x : nums) { if (!seen.add(x)) { seen.remove(x);Explore the full code

solution.javaJava

Hash Set — Add and Remove — reference

3 teaching notes

1
public int singleNumber(int[] nums) {
2
    Set<Integer> seen = new HashSet<>();
3
    for (int x : nums) {
4
        // add returns false if x was already present — meaning this is its second
5
        // appearance.
6
        if (!seen.add(x)) {
7
            // Second sighting cancels the first: remove it so only unpaired values
8
            // remain.
9
            seen.remove(x);
10
        }
11
    }
12
    // Exactly one value is left — the single number.
13
    return seen.iterator().next();
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One pass with O(1) average set operations is O(n) time; the set can hold up to n/2 + 1 distinct values, so O(n) space.

E · Edge cases and pitfalls5nums = [1] — 1 is added once and never removed; set = {1} → returns 1.Explore edge cases

Edge cases handled

nums = [1]1 is added once and never removed; set = {1} → returns 1.
nums = [-1, -1, 5]-1 added then removed, 5 added once → returns 5. Negatives are fine in a set.

Pitfalls

Using a frequency map instead of a presence set — same complexity but more code and the same O(n) space cost.
Forgetting the prompt's O(1)-space requirement and presenting this as the final answer.
Assuming the set is non-empty at the end without relying on the 'exactly one single' guarantee.

03.2

Approach 2 of 2 · Optimal

XOR All Elements (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'XOR cancels pairs because a ^ a = 0, so the single survivor falls out for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Is there a single arithmetic/bitwise operation where combining a value with itself produces nothing, so duplicates erase each other?

2Hint 2Explore hint

XOR has two key laws: x ^ x = 0 and x ^ 0 = x. What happens if you XOR every element of the array into one running total?

3Hint 3Explore hint

Fold the whole array with XOR starting from 0. Every value that appears twice contributes x ^ x = 0; the lone value contributes itself.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 1, 2, 1, 2]

Array state

x=4

acc: 0 ^ 4 = 4

x ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

XOR All Elements (Optimal) — optimal

3 teaching notes

1
public int singleNumber(int[] nums) {
2
    // Seed with XOR's identity: 0 ^ x = x, so it starts neutral.
3
    int result = 0;
4
    for (int x : nums) {
5
        // Fold each element in. Pairs cancel (a ^ a = 0); the lone value survives.
6
        result ^= x;
7
    }
8
    // After all cancellations, only the single number's bits remain.
9
    return result;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single pass doing one constant-time XOR per element is O(n) time; only one integer accumulator is kept, so O(1) space.

E · Edge cases and pitfalls5nums = [1] — 0 ^ 1 = 1. The identity seed makes single-element arrays just work.Explore edge cases

Edge cases handled

nums = [1]0 ^ 1 = 1. The identity seed makes single-element arrays just work.
nums = [-2, -2, 3]XOR on two's-complement bits: -2 ^ -2 = 0, then 0 ^ 3 = 3. Negatives cancel identically.

Pitfalls

Seeding the accumulator with nums[0] and looping from index 1 — works, but seeding 0 and looping all is cleaner and avoids an empty-array crash.
Trying to extend this to 'each appears three times' — XOR only cancels even counts; that variant needs per-bit counting mod 3.
Confusing XOR (^) with OR (|) or AND (&) — only XOR has the self-cancelling property.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int singleNumber(int[] nums) { int result = 0; for (int x : nums) { result ^= x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using a hash set as the final answer

It's O(n) space, but the prompt explicitly demands O(1). It signals you don't know XOR's cancellation property.

Explore the code comparison

Don't write this

seen = set()
for x in nums:
    if x in seen:
        seen.remove(x)
    else:
        seen.add(x)
return seen.pop()

Write this instead

result = 0
for x in nums:
    result ^= x
return result

Using OR instead of XOR

OR accumulates bits but never clears them, so duplicates don't cancel — you get the bitwise-OR of all values, not the single one.

Explore the code comparison

Don't write this

int result = 0;
for (int x : nums) {
    result |= x;   // OR never cancels pairs
}
return result;

Write this instead

int result = 0;
for (int x : nums) {
    result ^= x;   // XOR cancels every pair
}
return result;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

XOR cancellation (pair annihilation)

Code pattern to memorize

result = 0
for x in nums:
    result ^= x   # pairs cancel to 0, single survives
return result

Rules to remember

1Seed the accumulator at 0, the XOR identity: 0 ^ x = x.
2The two laws that make this work: a ^ a = 0 (self-cancel) and a ^ 0 = a (identity).
3XOR is commutative and associative, so order doesn't matter — every duplicate finds its partner no matter where it sits.
4This needs O(1) space — if you reach for a hash set you've solved it, but not optimally.
5XOR only cancels things that appear an even number of times. The 'twice' guarantee is load-bearing.

Use this pattern when

Every element repeats an even number of times except one
You need O(1) space and the values fit in a fixed-width int
Phrasing like 'find the element that appears once / an odd number of times'
You can stream the input — one pass, no storage

Choose another pattern when

Elements repeat three times except one → XOR cancels pairs, not triples (Single Number II needs bit counting)
Two unique elements instead of one → XOR gives a^b combined, needs a split step (Single Number III)
Need the count of how many times each value appears → hash map
Values aren't integers (strings, objects) → XOR doesn't apply

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Single Number II
Coming soon
Every element appears three times except one. XOR can't cancel triples — count each bit mod 3.
Single Number III
Coming soon
Two unique elements. XOR everything to get a^b, then use a set bit of a^b to split into two groups.
Missing Number
Same XOR-cancellation idea: XOR all indices with all values; the missing number survives.
Find the Difference
Coming soon
XOR every character of both strings; the extra letter is the lone survivor.

Same pattern

Continue · Next problem

Number of 1 Bits