Koko Eating Bananas
Problem Description
Koko loves to eat bananas. There are n piles of bananas, the ith 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.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Constraints:
- 1 <= piles.length <= 104
- piles.length <= h <= 109
- 1 <= piles[i] <= 109
Solve it on LeetCode
Approaches
1. Brute Force Solution
Intuition:
In this approach, we try every possible eating speed k starting from 1 until we find a speed that allows Koko to eat all the bananas within h hours. For each speed, we simulate the eating process and check if Koko can finish all bananas within h hours.
Code:
- Time Complexity: We may have to try all speeds from 1 to the maximum pile size, leading to
O(max(piles) * n), wherenis the number of piles. - Space Complexity:
O(1), no additional space other than input and local variables.
2. Binary Search Solution
Intuition:
Using binary search, we efficiently narrow down the range of Koko's possible eating speeds. Instead of checking each speed one by one, we continuously adjust our search range based on whether the current mid speed allows Koko to eat all bananas in h hours. The goal is to find the minimal speed k that works.
Code:
- Time Complexity:
O(n log(max(piles))), wherelog(max(piles))is for the binary search andnfor each check ofcanEatAllBananas. - Space Complexity:
O(1), using only a constant amount of extra space.