Free Math and bits lessonsMath and bits · Stage 2 · Bits · Step 3

Pairs cancel out

Find the one value without a partner by XOR-ing everything together. About 8 minutes.

XOR compares bit by bit

XOR is a spot-the-difference game: the result has a 1 wherever the two inputs differ. A number compared with itself shows no difference, so it gives 0. Compared with 0 nothing changes, so you get the number back.

Order does not matter either, so 5 XOR 9 XOR 5 is just 9: the two 5s cancel.

Same number twice: cancels to 0.

XOR with 0: changes nothing.

In code

5 ^ 5       # 0
5 ^ 0       # 5
5 ^ 9 ^ 5   # 9

nums = [4, 1, 2, 1, 2] · XOR everything

acc: 4 (100)

acc = 0 ^ 4 = 4 (100 in binary).

Move 1 of 5

Let the pairs cancel

Imagine a room where everyone arrived in pairs except one person who came alone. If every pair shakes hands and leaves, the loner is left standing. XOR does that to numbers.

XOR the whole list together: each value that appears twice meets its partner and vanishes, and the one without a partner remains. No sets, no sorting, no extra memory.

Only works for pairs: a value seen three times would survive.

In code

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

Quick check

What is 4 ^ 1 ^ 2 ^ 1 ^ 2?

Show the answer

4. The 1s cancel and the 2s cancel, leaving 4.

Your problem

The number without a partner

Every value in a non-empty list appears exactly twice, except one that appears once. Return that one.

Example

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

1 ≤ n ≤ 1,000,000 (n odd) · values may be negative · use O(1) extra memory

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.