Pattern visualizer
Missing Number
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. Animated on: nums = [3,0,1], n = 3 — find the missing number in [0, n]..
Expected sum minus actual sum
time O(n)space O(1)step 1 / 8
3
[0]0
[1]1
[2]line 1
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) / 23 actualSum = 04 FOR each num in nums:5 add num to actualSum6 RETURN expectedSum - actualSum
← / → step · space play · Home restart