Back to Binary Search
Medium
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.
Examples
Input:piles = [3,6,7,11], h = 8
Output:4
With speed 4, it takes ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3 hours. Total = 1+2+2+3 = 8 hours.
Input:piles = [30,11,23,4,20], h = 5
Output:30
With speed 30, it takes exactly 1 hour for each pile. Total = 5 hours.
Constraints
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
Approach
Start with a speed of `k = 1`. Check if Koko can eat all bananas within `h` hours at this speed. If not, increment `k` and try again until a valid speed is found.
Complexity Analysis
Time Complexity
O(n * max(p))
Space Complexity
O(1)
This will cause a Time Limit Exceeded (TLE) error since max(p) can be 10^9.
Solution.java
class Solution { public int minEatingSpeed(int[] piles, int h) { int k = 1; while (true) { long hours = 0; for (int pile : piles) { hours += Math.ceil((double) pile / k); } if (hours <= h) { return k; } k++; } }}