Koko Eating Bananas

The key idea

The answer is monotonic: if speed k finishes in time, every speed faster than k also finishes in time. So we binary search the smallest k in the range 1..max(piles) whose total hours fit within h.

Problem

Koko loves bananas. There are n piles of bananas, where the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko decides her constant eating speed of k bananas per hour. Each hour she chooses one pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and will not eat any more bananas during that hour.

Koko likes to eat slowly but still wants to finish all the bananas before the guards return. Return the minimum integer speed k such that she can eat all the bananas within h hours.

Constraints

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

Examples

Input: piles = [3,6,7,11], h = 8 Output: 4

Input: piles = [30,11,23,4,20], h = 5 Output: 30

Input: piles = [30,11,23,4,20], h = 6 Output: 23

Complexity

Time: O(n log m) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →