136. Single Number — DSA Atlas

136

EasyBit ManipulationBitwise XOR accumulatorXOR cancellation

Single Number

Given a non-empty array nums in which every element appears exactly twice except for one element that appears once, find and return the single element. Solve it with linear time and constant extra space.

Open official problem prompt ↗

In plain English

Identify the one value that lacks a partner, using no extra data structure and a single pass.

Picture it like this

Pairing up socks by tossing each matching pair into the trash; whatever sock remains at the end is the odd one out.

Example

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Why: 1 and 2 each appear twice and cancel out; 4 is the only unpaired value.

Constraints

1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4Each element appears twice except one which appears onceMust run in O(n) time and O(1) extra space

Pattern lesson

See the pattern, then code

XOR cancellation

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. XOR is commutative and associative, and any number XORed with itself is 0. XORing the whole array pairs off the duplicates into 0, leaving only the lone element.

New words, made simpleKnow these before the algorithm

XOR (^): Bitwise exclusive-or; outputs 1 where the two bits differ.
Self-inverse: A property where applying an operation twice cancels it: a ^ a = 0 and a ^ 0 = a.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash set / count map

Correct but uses extra memory, violating the O(1) space goal.

Count occurrences, then return the value seen once.

Time O(n)Space O(n)

Best choiceXOR fold

Optimal in both time and space with a one-line loop.

XOR all numbers together so pairs cancel.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing a prefix of nums, result equals the XOR of that prefix, which equals the XOR of the values that have appeared an odd number of times so far.

Why this is correct

Reasoning

Because XOR is associative and commutative, the order does not matter; grouping equal values, each duplicated pair contributes a ^ a = 0. All pairs vanish, and 0 XORed with the single value yields that value.

The algorithm in three movesSay these aloud before coding

1Initialize an accumulator result = 0

acc=0^4=4

2XOR every element of nums into result

acc=4^1=5

3Return result, which holds the unpaired value

acc=5^2=7

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readresult=0

2 · AskXOR next?

3 · Update stateresult=0

4 · Resultread 4

Key takeaway

Running XOR: the two 1s and two 2s cancel, leaving 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Accumulator
Start at 0, the identity element for XOR.
2
Lines 4-5Fold the array
XOR each element in; duplicates cancel, the singleton survives.
3
Lines 6Return
The accumulator now equals the unpaired value.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-element array returns that element
Negative values work because XOR is defined bitwise regardless of sign
Zero can be the single number or a duplicate — both handled

Common beginner mistakes

Reaching for a hash map and losing the O(1)-space property
Trying to sum and subtract, which can overflow in fixed-width languages and fails when duplicates appear more than twice
Confusing XOR (^) with exponentiation or logical or

Check your understanding

Would the XOR trick still work if the single element could be negative?

Single Number

Single Number

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation