Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Missing Number

LeetCode #268Easy
XOR index ⊕ value · pairs cancel

An array contains n distinct numbers drawn from the range [0, n]. Exactly one number in that range is missing — find it using O(1) extra space.

Asked atAmazonMicrosoftBloomberg
step 1 / 16
0
0
0
0
[0][1][2][3]
Sum formula
▸
1expected ← n·(n+1)/2
2expected ← n·(n+1)/2
3for x in nums: actual ← actual + x
4return expected − actual
state
  • nums[3, 0, 1]
  • n3
  • range[0, 3]

line 1The array holds the numbers 0..n with exactly one missing. If they were ALL present, their sum would be 0+1+…+n = n(n+1)/2. Whatever is missing is the gap between that expected sum and the actual array sum.