Koko Eating Bananas
Problem
There are several piles of bananas and Koko has h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it; if the pile has fewer, she finishes it and waits out the hour. Find the smallest integer speed k that lets her clear every pile within h hours.
Examples
Constraints
- • 1 <= piles.length <= 10^4
- • piles.length <= h <= 10^9
- • 1 <= piles[i] <= 10^9
Hints & approach
Hint 1
If Koko can finish at speed k, can she also finish at speed k + 1?
Hint 2
The feasible speeds form a contiguous range, so binary search on k itself.
Hint 3
For a given k, the hours needed are the sum of ceil(pile / k).
Approachtry the hints first
Instead of searching an array, binary search over possible answers. Speeds range from 1 to max(piles), and feasibility is monotonic: any speed above a working speed also works. For a candidate k, compute total hours as the sum of ceil(p / k) over all piles (use (p + k - 1) / k with integers). If that fits in h, try slower speeds (hi = k); otherwise go faster (lo = k + 1). The loop converges on the minimum feasible speed.
Time O(n log m), m = max pile · Space O(1)