Missing Number
- Whiteboard
whiteboard-Medium
- Challenge
coding-challenge-Easier
- Concepts
Runtime, General
- Download
- Solution
Imagine a list of numbers from 1 to max_num, inclusive – except that one of these numbers will be missing from the list.
You should write a function that takes this list of numbers, as well as the max_num, and it should return the missing number.
For example, given a list of numbers, in random order, of 1..10, 8 was removed. Your function would be given the list and the max_num (10), and it should find 8:
>>> missing_number([2, 1, 4, 3, 6, 5, 7, 10, 9], 10)
8
This needs to work even if the list isn’t in increasing order:
>>> missing_number([2, 1, 4, 3, 6, 5, 7, 10, 9], 10)
8
If no numbers are missing, return 0.
Step 1 (easiest)
Initially, focus on reducing runtime—this should be solvable in O(n) time. You can create an additional list/set/dictionary if necessary.
Write a version that uses a straightforward solution and runs in O(n) time.
Step 2 (harder)
Now, think about reducing memory use—did your first solution require you to keep a new list/set/dictionary? Can you think of a different way to think about the problem that doesn’t use additional memory, even if it takes more time?
There’s a way you could solve this in O(n log n) time that doesn’t require creating another large data structure (technically, while being O(n log n) in runtime, it is O(1) in “runspace”—it uses the same amount of memory no matter how big n is)
Need a hint?
O(n log n)
What kinds of algorithms commonly have this runtime?
Step 3 (a little tricky!)
There’s a solution that has O(n) runtime and O(1) runspace, but it requires a bit of creative thinking about the problem from a math perspective. See if you can find it.