Missing Number

Expected sum minus actual sum

time O(n)space O(1)

The numbers 0..n should sum to n*(n+1)/2. If exactly one of them is missing from the array, the actual sum falls short by precisely that number — so expectedSum minus actualSum reveals it directly, with no sorting or hashing needed.

Details

Animated on: nums = [3,0,1], n = 3 — find the missing number in [0, n].

Problem:Missing NumberEasy

Pattern:Bit Manipulation

Expected sum minus actual sum

step 1 / 8

[0]

[1]

[2]

nums = [3,0,1], n = 3. Sum every value in nums, then compare it to the expected sum of 0..n.

Pseudocode

1FUNCTION missingNumber(nums, n):
2  expectedSum = n * (n + 1) / 2
3  actualSum = 0
4  FOR each num in nums:
5    add num to actualSum
6  RETURN expectedSum - actualSum

← / → step · space play · Home restart

Every step in words

Show all 8 steps

nums = [3,0,1], n = 3. Sum every value in nums, then compare it to the expected sum of 0..n.
num = 3. actualSum = 0 + 3 = 3.
num = 0. actualSum = 3 + 0 = 3.
num = 1. actualSum = 3 + 1 = 4.
actualSum = 4 — every value in nums has now been summed.
expectedSum = n*(n+1)/2 = 3*4/2 = 6 (the sum of every number 0..3).
missing = expectedSum - actualSum = 6 - 4 = 2.
The gap between 6 and 4 is the one number from 0..3 that never appeared in nums. Missing number = 2.

Now solve it yourself

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

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