The problem
Koko eats bananas at speed k per hour; each pile takes ⌈pile / k⌉ hours. Find the minimum k that finishes all piles within h hours.
Stuck? Reveal hints one at a time
How to approach it
- 1Define hours(k) = Σ ceil(pile / k).
- 2Binary search k in [1, max(pile)]: if hours(mid) ≤ h, the answer is mid or smaller → hi = mid; else lo = mid + 1.
- 3Loop until lo === hi; that is the minimum feasible speed.
Key insight
"Binary search on the answer" needs only a monotonic yes/no predicate — the sorted thing is the implicit feasibility function, not any array.
The solution
Watch out for
- Integer ceil: (pile + k − 1) // k avoids float precision issues on huge piles.
- The lower bound is 1, not min(pile) — tiny piles still take a full hour each.