Find the Smallest Divisor Given a Threshold
Real-world version: Smallest Binder Comb for the Pass BudgetThe statement here is our own: the same inputs, outputs and technique.
A print shop binds jobs on a comb machine. pages[i] is the page count of job i, and every job is bound on its own.
A comb of size d grips at most d pages per pass, so job i occupies ceil(pages[i] / d) passes: the machine keeps taking full bites of d pages and a final short bite still uses up a whole pass.
Combs are stocked in every whole size from 1 upward, and the shop is prepared to run at most budget passes in total across all the jobs. Return the smallest comb size that keeps the total number of passes at or below budget.
budget is never smaller than the number of jobs, so some comb size always works.
Examples
Example 1
- Input
- pages = [5, 7], budget = 4
- Output
- 4
A comb of 4 takes job 0 in two passes, of 4 pages then 1, and job 1 in two passes, of 4 pages then 3. That is 4 passes altogether, which the budget allows.
Example 2
- Input
- pages = [4, 8, 12], budget = 6
- Output
- 4
A comb of 4 grips job 0 in a single pass, job 1 in two and job 2 in three, for exactly 6 passes.
Example 3
- Input
- pages = [17], budget = 1
- Output
- 17
A comb of 17 binds the one 17-page job in a single pass, which fits a budget of 1 pass.
Constraints
- 1 <= pages.length <= 5 * 10^4
- 1 <= pages[i] <= 10^6
- pages.length <= budget <= 10^6
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_binder_comb(pages: list[int], budget: int) -> int:public int smallestBinderComb(int[] pages, int budget)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 9 test cases: 9 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's