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

Cancel against what should be there

Find the missing number from 0 to n by XOR-ing the list with the full range. About 7 minutes.

Create the partners yourself

The list should hold every number from 0 to n, but one is missing. The missing value has no partner, so make partners for everyone else: XOR in every number from 0 to n, then XOR in every value that is in the list.

A value that is both expected and present cancels out. The missing one was expected but never showed up, so it is the one that survives.

Expected numbers plus present numbers: all XORed together.

In code

result = len(nums)
for i, x in enumerate(nums):
    result ^= i ^ x
return result

0..3 and then nums = [3, 0, 1], all XORed together

acc: 0

First XOR every number from 0 to n = 3: 0 ^ 1 ^ 2 ^ 3 = 0.

Move 1 of 5

No overflow, no extra memory

Adding up 0 to n and subtracting the sum of the list also works, but for huge lists the sum can overflow in some languages. XOR never grows beyond the bits already in use, so there is nothing to overflow.

The code starts from the list length because n itself is part of the range, then pairs each position with its value as it goes.

Remember n itself: the range goes up to n, one past the last position.

Quick check

nums = [3, 0, 1] (n = 3). What is 0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1?

Show the answer

2. 0, 1 and 3 each appear twice and cancel; 2 is left.

Your problem

Missing number, by XOR

A list of n different numbers holds every number from 0 to n except one. Return the missing one, using XOR and no extra memory.

Example

nums = [3, 0, 1] → 2

1 ≤ n ≤ 1,000,000

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