Missing Number
An array holds n distinct numbers from the range 0 … n. Find the one that is missing.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Subtract the array's sum from n(n + 1) / 2, or XOR every index with every value so that only the missing number survives.
Pattern: Bit manipulation & math. Use XOR, AND and shifts to work on the binary representation directly.
Complexity
| Measure | Bound |
|---|---|
| Time | O(n) |
| Extra space | O(1) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.