DSAMotivator

Single Number

Easy·🔢 Bit Manipulation·Open on LeetCode ↗

Every value in the array appears twice except one. Find the value that appears alone, using no extra memory.

nums = [7, 2, 5, 2, 7]step 1/7
7
2
5
2
7
0
1
2
3
4
accumulator
value
0
bits
0000

Start at zero and XOR everything in. Nothing is ever compared.

1def single_number(nums):
2    result = 0
3    for n in nums:
4        result ^= n
5    return result
Read the 7 steps as text
  1. 1Start at zero and XOR everything in. Nothing is ever compared.
  2. 20000 XOR 0111 = 0111, so the running value is 7.
  3. 30111 XOR 0010 = 0101, so the running value is 5.
  4. 40101 XOR 0101 = 0000 — that pair has cancelled itself out.
  5. 50000 XOR 0010 = 0010, so the running value is 2.
  6. 60010 XOR 0111 = 0101, so the running value is 5.
  7. 7Every pair cancelled. What survives is the unpaired value: 5.

The idea

A hash set solves this immediately, and it's a perfectly good first answer — but it costs O(n) memory, and the problem specifically asks for constant space. That constraint is a hint about which tool is wanted.

XOR has three properties that, taken together, are the whole solution. A value XOR'd with itself is 0. Anything XOR'd with 0 is unchanged. And XOR is both commutative and associative, so the order you combine things in does not matter.

That last one is what makes the pairs cancel even though they're scattered. XOR-ing the entire array is the same as first grouping each pair together — every pair collapses to 0, all those zeros collapse to 0, and the lone value passes through untouched.

So the answer isn't found, it's accumulated. There is no comparison anywhere in the algorithm.

The approach

  1. 1Start an accumulator at 0.
  2. 2XOR every element into it, in whatever order the array happens to be in.
  3. 3Whatever remains is the unpaired value.

Complexity

Time
O(n)
Space
O(1)

One pass and one integer, regardless of how large the values are.

Code

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

What goes wrong

  • •Starting the accumulator at the first element and then XOR-ing it again in the loop, which cancels it out.
  • •Assuming this generalises. If elements appear three times instead of two, XOR no longer cancels them and you need bit-counting modulo 3 — a genuinely different technique with the same flavour.
  • •Using `+` and `−` instead. It works only if you already know the distinct values, which you don't.