The Missing Exam Paper
Before an exam you print one paper per student and number them 1, 2, 3 and so on. Afterwards the stack on your desk is one paper short: somebody walked out without handing theirs in.
The papers came back in whatever order students dropped them off. You want to know which number is missing without sorting the whole pile.
Your task
Write missingPaper(papers). You printed papers.length + 1 papers, numbered from 1 to papers.length + 1. The list holds every number except one, each at most once, in any order. Return the missing number.
If the list is empty, you printed a single paper, number 1, and it is the one missing.
missingPaper(papers: int[]) → int
Examples
papers = [4, 2, 5, 1]
3
Four papers came back, so five were printed: 1, 2, 3, 4, 5. Every number except 3 is on the desk.
papers = [1, 2, 3]
4
Four papers were printed. The pile goes 1, 2, 3 with no gap inside it, so the missing one is the last number, 4. Looking only for a gap between neighbours would miss this.
papers = []
1
Nothing came back, so only paper 1 was printed, and it is missing.
Constraints
- 0 ≤ papers.length ≤ 100,000
- 1 ≤ papers[i] ≤ papers.length + 1
- All numbers in papers are different, and exactly one number from the range is absent.
Start with brute force
For each number from 1 to n + 1, scan the pile to see if it is there. The first number you cannot find is the answer.
Each scan reads up to n papers, and you may do n + 1 scans. With 100,000 papers that is about 10 billion reads. Sorting first and looking for the gap is better, O(n log n), but it still does more work than the problem needs.
Hints
0 of 4 shown- Hint 1
Take the pile
[4, 2, 5, 1]. If no paper were missing, what would the numbers 1 to 5 add up to? What do the four papers you have add up to? - Hint 2
The full set adds to 15 and the pile adds to 12. Which paper does the difference stand for? Does the order of the pile change either total?
- Hint 3
You do not need to sort or store anything. The total of 1 to
mism × (m + 1) / 2, and one running sum gives you the rest. - Hint 4
Let
m = papers.length + 1. Start fromm × (m + 1) / 2and subtract each paper as you walk the list once. Whatever is left is the missing number.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
You know exactly what the full set looks like: every number from 1 to m. So you know its total before you look at a single paper. Each paper you hold accounts for part of that total, and the part nobody accounts for is the missing paper.
Trace [4, 2, 5, 1]. Here m = 5, and 1 + 2 + 3 + 4 + 5 = 5 × 6 / 2 = 15.
- Subtract 4: 11 left.
- Subtract 2: 9 left.
- Subtract 5: 4 left.
- Subtract 1: 3 left. Return 3.
Order never mattered, which is why no sort is needed. A hash set of the papers also works in O(n) time, but it costs O(n) memory to answer a question one number can answer. With 100,000 papers the total is about 5 billion: fine for JavaScript numbers and Python integers, but in a language with 32-bit integers you would need a 64-bit type.
function missingPaper(papers) {
const m = papers.length + 1; // how many were printed
let left = (m * (m + 1)) / 2; // 1 + 2 + ... + m
for (const p of papers) left -= p; // remove each paper we have
return left;
}def missing_paper(papers):
m = len(papers) + 1 # how many were printed
left = m * (m + 1) // 2 # 1 + 2 + ... + m
for p in papers: # remove each paper we have
left -= p
return leftRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.