Slowest Safe Scanner Speed
MediumBinary Search
Problem
An archive must digitise several boxes of documents; boxes[i] is the number of pages in box i. The scanner is set to a speed of k pages per hour. Each hour it works on one box only: it scans k pages of it, or the rest of the box if fewer remain, and stays idle for the remainder of that hour.
Running fast wears the machine, so return the smallest integer speed k that finishes every box within hours hours.
Example 1
- Input:
- boxes = [6, 9, 14], hours = 7
- Output:
- 5
At 5 pages/hour the boxes take 2 + 2 + 3 = 7 hours. At 4 they take 2 + 3 + 4 = 9.
Example 2
- Input:
- boxes = [12, 1, 7], hours = 3
- Output:
- 12
With as many hours as boxes, each box must be done in one hour.
Example 3
- Input:
- boxes = [2, 2, 2, 2], hours = 8
- Output:
- 1
Constraints
- 1 ≤ boxes.length ≤ 10^4
- boxes.length ≤ hours ≤ 10^9
- 1 ≤ boxes[i] ≤ 10^9
Hint
Show the first hint
For a fixed speed k, how many hours does one box of p pages take?
Walkthrough
How to approach it
01Clarify before coding
- Can the scanner switch boxes mid-hour? No: leftover time in an hour is wasted, hence the ceiling.
- Is there always an answer? Yes, hours ≥ number of boxes, so k = max(boxes) always works.
- Must k be an integer? Yes.
02Brute force
Try k = 1, 2, 3, ... and return the first k whose total hours fit.
Cost: O(n · max(boxes)): up to 10^4 × 10^9 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.