Koko Eating Bananas
Koko eats bananas at k per hour. Each hour she picks one pile and eats up to k from it; if the pile has fewer, she finishes it and waits. Find the smallest k that lets her finish all piles within h hours.
Intuition
There is no formula that produces k directly, but given a candidate k we can check it in one linear pass: sum ceil(pile / k) over all piles and compare with h. And feasibility is monotonic — if speed k works, every speed above it works too, and everything below some threshold fails. That monotonic boundary is exactly what binary search locates, except we search the space of possible answers (1 to the largest pile) rather than the array itself.
Approach
Bound the answer and note that it is checkable
Koko never benefits from eating faster than the largest pile — she can only eat from one pile per hour, so any speed above max(piles) finishes in exactly the same number of hours. And she must eat at least 1 per hour. So the answer lies in [1, max(piles)]. Separately, testing a candidate is easy: at speed k a pile of size p takes ceil(p / k) hours, because the last partial hour still costs a full hour.
Establish monotonicity — the property that unlocks binary search
If speed k finishes in time, does k + 1? Yes: every pile takes the same number of hours or fewer, so the total can only drop. Equally, if k is too slow, so is everything below it. So the hours-needed function is non-increasing in k, and the feasible speeds form a suffix of the range: [answer, max(piles)]. Finding the first feasible value in a sorted yes/no sequence is precisely binary search.
Binary search the speed, not the array
Set lo = 1, hi = max(piles). Take the midpoint, run the O(n) hours check. If it fits within h, record it and move hi down to search for something slower — we want the smallest feasible speed. If it does not fit, move lo up. When the pointers cross, the recorded best is the answer. Cost: O(n log max(piles)), which for a million piles and billion-sized piles is about thirty linear passes.
Solution & live demo
Edge cases
She has exactly one hour per pile, so k must be max(piles). The binary search converges there naturally — nothing smaller is feasible.
The answer is 1, the lower bound of the search space. The check at k = 1 succeeds and the search drives hi all the way down.
The ceil division handles it; with h hours available the answer is ceil(pile / h), which the search finds without special-casing.
Using pile // k instead of ceil silently under-counts and accepts speeds that are too slow. Use -(-p // k) in Python or (p + k - 1) // k to round up.