Missing Number
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
An array holds n distinct numbers from 0 to n. Find the one missing number.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What should 0 + 1 + ... + n equal?
- Hint 2Compare with the sum of the array.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A class register of students numbered 0 to n, and one is absent. Add up every roll number you saw in the room. The register says the full class would add up to n(n + 1) / 2. The difference between the two totals is the absent student's number.
- The obvious way
Sort and look for the gap: O(n log n). Or a set: O(n) space.
- The key insight
n = len(nums). The expected total is n x (n + 1) / 2. Return expected minus the sum of the array.
- The algorithm
- n = length of the array.
- expected = n(n + 1) / 2.
- actual = sum of the array.
- Answer = expected - actual.
Watch it run
Examplenums = [3, 0, 1]
n = 3, so the students should be 0, 1, 2, 3: the register total is 3 x 4 / 2 = 6.
expected = 6
Where people slip
- The range is 0..n, so the expected total uses n(n + 1) / 2 with n = len(nums).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def missing_number(nums):
n = len(nums)
expected = n * (n + 1) // 2 # what the full register adds up to
return expected - sum(nums) # the shortfall is the absent studentNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.