Single Number

XOR cancels every pair, leaving only the odd one out

time O(n)space O(1)

XOR has two properties that make this a one-line trick: x^x = 0 (a number cancels itself out) and x^0 = x (XOR with nothing changes nothing), and XOR doesn't care about order. So if you XOR every number in the array together, every PAIR cancels to 0, and whatever's left over is the single number that never had a partner to cancel with. No extra memory needed to track counts.

Details

Animated on: nums = [4,1,2,1,2] — every number appears twice except one, find it

Problem:Single NumberEasy

Pattern:Bit Manipulation

XOR cancels every pair, leaving only the odd one out

step 1 / 7

[0]

[1]

[2]

[3]

[4]

Start with result=0. XOR with 0 changes nothing, so this is a safe starting point.

i=0· arr[0] = 4

Pseudocode

1FUNCTION singleNumber(nums):
2  result = 0
3  FOR each n in nums:
4    result = result XOR n
5  END FOR
6  RETURN result
7END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 7 steps

Start with result=0. XOR with 0 changes nothing, so this is a safe starting point.
result = 0 ^ 4 = 4. First number, nothing to cancel yet.
result = 4 ^ 1 = 5 (binary: 100 ^ 001 = 101).
result = 5 ^ 2 = 7 (binary: 101 ^ 010 = 111).
result = 7 ^ 1 = 6 (binary: 111 ^ 001 = 110) — the SECOND 1 just cancelled the first one's bit back out.
result = 6 ^ 2 = 4 (binary: 110 ^ 010 = 100) — the SECOND 2 cancels the first 2's bit as well. Only 4's bit survives.
Array exhausted. Every pair (1,1) and (2,2) cancelled to 0 along the way — only 4 never had a partner, so it's the answer.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Single Number in the editor All Bit Manipulation problems Back to roadmap