Loading…

easyBasicsSometimes asked

Odd-Occurring Number

Basics · 6 min

Given an array where every number appears an even number of times except one that appears an odd number of times, find that number.

In plain English

XOR of all elements cancels the even-occurring ones (x ^ x = 0), leaving only the odd one.

Examples

Example 1

Input: nums = [1, 2, 1, 2, 3]
Output: 3
Note: 3 appears once.

Example 2

Input: nums = [4, 4, 7]
Output: 7
Note: 7 is odd-count.

Example 3

Input: nums = [9]
Output: 9
Note: Single element.

Constraints

1 ≤ nums.length ≤ 10^5
Exactly one element has odd count

Clarifying questions1First question: Exactly one odd-count element?Explore questions

Q1.Exactly one odd-count element?
Yes; multiple would need a different XOR partition trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

XOR every element together; pairs cancel to 0 and the result is the odd-occurring number. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the XOR-cancellation trick for O(1) space.

Where candidates slip

Reaching for a frequency map instead of XOR.

How to stand out

State the x^x=0 / x^0=x properties that make it work.

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.

03.1

Approach 1 of 1 · Optimal

XOR accumulation

TimeO(n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What property of XOR makes pairs disappear?

2Hint 2Explore hint

Fold all elements with XOR — what survives?

3Hint 3Explore hint

Can you do it without a hash map (O(1) space)?

A · Core idea

Every value appears an even number of times except one. XOR all elements together: even occurrences cancel to 0, leaving the odd-count value. O(n) time, O(1) space.

Why XOR cancels even occurrences. XOR has two key properties: x ^ x = 0 (a value XOR'd with itself vanishes) and x ^ 0 = x. A value appearing an even number of times pairs up and cancels to 0; the value appearing an odd number of times has one un-cancelled copy left. XOR is also commutative/associative, so order doesn't matter.

Why XOR beats a hash map. A frequency map also works but costs O(n) extra space. The XOR fold needs a single accumulator — O(1) space — which is the answer the interviewer is after.

Seed at 0. Start the accumulator at 0 (the XOR identity) so the first element folds in cleanly.

B · Visual dry run

Interactive dry run

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

nums = [1, 2, 1, 2, 3]

1^2^1^2

the two 1s and 2s cancel

State0

Final result3

C · Code with teaching comments

solution.javaJava

XOR accumulation — optimal

1 teaching note

1
public int oddOccurring(int[] nums) {
2
    int x = 0;
3
    // Even occurrences cancel; the odd one remains.
4
    for (int v : nums) x ^= v;
5
    return x;
6
}

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

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

This O(1)-space XOR trick is the same one behind 'Single Number' — recognising it is the whole point.

ComplexityO(n) time, O(1) space — one XOR per element with a single accumulator — O(n) time, O(1) space.

E · Edge cases and pitfalls4nums = [4, 4, 7] — 4s cancel → 7.Explore edge cases

Edge cases handled

nums = [4, 4, 7]4s cancel → 7.
nums = [9]Single element → 9.

Pitfalls

Using a hash map (O(n) space) when XOR is O(1).
Initialising the accumulator to something other than 0.

Practice

Try the solution yourself

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

Editable code previewpublic int oddOccurring(int[] nums) { int x = 0; for (int v : nums) x ^= v; return 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 map (O(n) space) when XOR is O(1).
Initialising the accumulator to something other than 0.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

XOR cancellation

Code pattern to memorize

x = 0; for v: x ^= v; return x

Rules to remember

1x ^ x = 0.
2x ^ 0 = x.
3XOR all → odd one.

Use this pattern when

Odd-count / unpaired element
Pairing cancellation

Interview takeaway

XOR all elements to isolate the odd-count value 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 Number
The 'appears twice except one' twin.
Single Number III
Coming soon
Two odd-count values — partition by a differing bit.

Same pattern

easyBasicsSometimes asked

Odd-Occurring Number

Basics · 6 min

Given an array where every number appears an even number of times except one that appears an odd number of times, find that number.

In plain English

XOR of all elements cancels the even-occurring ones (x ^ x = 0), leaving only the odd one.

Examples

Example 1

Input: nums = [1, 2, 1, 2, 3]
Output: 3
Note: 3 appears once.

Example 2

Input: nums = [4, 4, 7]
Output: 7
Note: 7 is odd-count.

Example 3

Input: nums = [9]
Output: 9
Note: Single element.

Constraints

1 ≤ nums.length ≤ 10^5
Exactly one element has odd count

Clarifying questions1First question: Exactly one odd-count element?Explore questions

Q1.Exactly one odd-count element?
Yes; multiple would need a different XOR partition trick.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

XOR every element together; pairs cancel to 0 and the result is the odd-occurring number. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the XOR-cancellation trick for O(1) space.

Where candidates slip

Reaching for a frequency map instead of XOR.

How to stand out

State the x^x=0 / x^0=x properties that make it work.

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.

03.1

Approach 1 of 1 · Optimal

XOR accumulation

TimeO(n)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What property of XOR makes pairs disappear?

2Hint 2Explore hint

Fold all elements with XOR — what survives?

3Hint 3Explore hint

Can you do it without a hash map (O(1) space)?

A · Core idea

Every value appears an even number of times except one. XOR all elements together: even occurrences cancel to 0, leaving the odd-count value. O(n) time, O(1) space.

Why XOR beats a hash map. A frequency map also works but costs O(n) extra space. The XOR fold needs a single accumulator — O(1) space — which is the answer the interviewer is after.

Seed at 0. Start the accumulator at 0 (the XOR identity) so the first element folds in cleanly.

B · Visual dry run

Interactive dry run

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

nums = [1, 2, 1, 2, 3]

1^2^1^2

the two 1s and 2s cancel

State0

Final result3

C · Code with teaching comments

solution.javaJava

XOR accumulation — optimal

1 teaching note

1
public int oddOccurring(int[] nums) {
2
    int x = 0;
3
    // Even occurrences cancel; the odd one remains.
4
    for (int v : nums) x ^= v;
5
    return x;
6
}

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

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

This O(1)-space XOR trick is the same one behind 'Single Number' — recognising it is the whole point.

ComplexityO(n) time, O(1) space — one XOR per element with a single accumulator — O(n) time, O(1) space.

E · Edge cases and pitfalls4nums = [4, 4, 7] — 4s cancel → 7.Explore edge cases

Edge cases handled

nums = [4, 4, 7]4s cancel → 7.
nums = [9]Single element → 9.

Pitfalls

Using a hash map (O(n) space) when XOR is O(1).
Initialising the accumulator to something other than 0.

Practice

Try the solution yourself

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

Editable code previewpublic int oddOccurring(int[] nums) { int x = 0; for (int v : nums) x ^= v; return 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 map (O(n) space) when XOR is O(1).
Initialising the accumulator to something other than 0.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

XOR cancellation

Code pattern to memorize

x = 0; for v: x ^= v; return x

Rules to remember

1x ^ x = 0.
2x ^ 0 = x.
3XOR all → odd one.

Use this pattern when

Odd-count / unpaired element
Pairing cancellation

Interview takeaway

XOR all elements to isolate the odd-count value 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 Number
The 'appears twice except one' twin.
Single Number III
Coming soon
Two odd-count values — partition by a differing bit.

Same pattern