260. Single Number III

260

MediumBit ManipulationBit manipulation with XORXOR partition by distinguishing bit

Single Number III

In an array where every element appears exactly twice except for two elements that each appear once, find those two single elements. The answer may be returned in any order, and the solution must run in linear time using constant extra space.

Open official problem prompt ↗

In plain English

Recover the only two non-repeating values from a stream where everything else is duplicated, using no auxiliary storage.

Picture it like this

Imagine matching socks tumbling out of a dryer. Pair them up and they vanish from consideration; you are left holding two odd socks. To tell them apart you find one feature where they differ (say, one has a stripe) and sort by that feature so each odd sock lands in its own pile.

Example

Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Why: 1 and 2 each appear twice and cancel; 3 and 5 are the two that appear only once.

Constraints

2 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1Each integer appears exactly twice except two that appear onceThe result can be returned in any order

Pattern lesson

See the pattern, then code

XOR partition by distinguishing bit

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. XOR of the whole array leaves a ^ b, the XOR of the two unique numbers. Because a != b, that combined value has at least one set bit, and at that bit a and b differ. Splitting the array by that single bit puts a in one group and b in the other, while every duplicate pair stays together, so a separate XOR of each group isolates one answer.

New words, made simpleKnow these before the algorithm

XOR (^): Bitwise exclusive-or; x ^ x = 0 and x ^ 0 = x, so equal pairs cancel.
Lowest set bit: The rightmost 1 bit of a number, extracted with x & -x.
Two's complement negation: -x flips all bits and adds one, which is why x & -x isolates the lowest 1.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash-map counting

Correct but violates the O(1) space requirement.

Count occurrences and return the two keys with count 1.

Time O(n)Space O(n)

Best choiceXOR then split by a differing bit

Meets both the time and constant-space bars.

XOR everything to get a ^ b, pick a bit where they differ, and XOR each partition separately.

Time O(n)Space O(1)

The rule we keep true

Invariant

Within each partition, every duplicated value appears an even number of times (both copies share the same bit), so it cancels, leaving exactly the one unique number assigned to that partition.

Why this is correct

Reasoning

a ^ b is nonzero because a != b, so it has a set bit where they differ. Duplicates always fall entirely into one side (both copies have identical bits), so they cancel in that side's XOR. a and b land on opposite sides by construction, so each side's XOR reduces to a single unique value.

The algorithm in three movesSay these aloud before coding

1XOR all elements to get axb = a ^ b

axb = 1^2^1^3^2^5 = 6 (110)

2Isolate the lowest set bit of axb with axb & -axb

lowbit = 6 & -6 = 2 (010)

3Partition numbers by whether that bit is set, XOR-ing each group

bit set -> {2,3,2}: 3 ; bit clear -> {1,1,5}: 5

4Return the two group results

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read1,2,1,3,2,5

2 · AskWhat is a ^ b?

3 · Update stateaxb accumulates to 6 (110)

4 · ResultPairs 1,1 and 2,2 cancel, leaving 3^5=6

Key takeaway

After all pairs cancel, the leftover XOR splits the array into the two groups that each hold exactly one unique number.

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 3-5Fold everything with XOR
All duplicated pairs cancel, so axb ends as a ^ b.
2
Lines 6Pick a distinguishing bit
axb & -axb isolates the lowest bit where a and b differ, guaranteeing they separate.
3
Lines 7-12Partition and reduce
Each group's XOR cancels its duplicates and leaves the one unique member.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

The two singles differ only in the highest bit — still handled, any differing bit works
Negative numbers — two's complement makes x & -x still valid
Array of length exactly 2 with two distinct singles returns them directly

Common beginner mistakes

Trying to use axb directly without partitioning, which only gives a ^ b, not a and b
Using x & (x-1) (which clears the lowest bit) instead of x & -x (which isolates it)
Assuming a fixed output order — LeetCode accepts either order but a strict equality test in local code may confuse you

Check your understanding

Why must a ^ b have at least one set bit?

Single Number III

Single Number III

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