DSA problem
Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Return the minimum integer k such that she can eat all the bananas within h hours.
This is a foundational "binary search the answer" problem. Direct simulation over candidate speeds is too slow (max(piles) can be up to 10^9), but the predicate canFinish(k) — "can Koko eat everything within h hours at speed k?" — is monotonic: if speed k works, every larger k also works. So the valid speeds form a contiguous suffix [k*, ∞) and binary searching for k* is well-defined.
The predicate is simple: for speed k, the i-th pile takes ceil(piles[i] / k) hours. Sum that over all piles and check whether it is at most h. The search range for k is [1, max(piles)] — the lower bound is 1 because k must be positive, the upper bound is max(piles) because at that speed every pile is finished in one hour, costing exactly n hours which is <= h by the constraint h >= n.
Use the lower-bound shape: lo = 1, hi = max(piles), while lo < hi set hi = mid if canFinish(mid) else lo = mid + 1. The result is the smallest feasible speed. The total work is O(n log M) where M = max(piles). Watch overflow: ceil(piles[i] / k) summed over many piles can exceed 32-bit when h is large; use long in Java/C++.
Examples
piles = [3,6,7,11], h = 84piles = [30,11,23,4,20], h = 530piles = [30,11,23,4,20], h = 623Constraints
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.