Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> 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:

piles = [3,6,7,11], h = 8

Output: 4

Example 2:

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

Output: 30

Example 3:

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

Output: 23

Koko Eating Bananas

This problem asks us to find the minimum eating speed k such that Koko can eat all bananas within h hours. We can use binary search to find the optimal k.

1. Naive Approach

A naive approach would be to iterate through all possible values of k from 1 to the maximum number of bananas in a pile and check if Koko can eat all the bananas within h hours for each k. This approach would have a time complexity of O(n * m), where n is the maximum number of bananas in a pile and m is the number of piles.

2. Optimal Solution

We can use binary search to find the optimal value of k. The lower bound for k is 1, and the upper bound is the maximum number of bananas in a pile. For each value of k in the binary search, we can calculate the number of hours it takes Koko to eat all the bananas. If the number of hours is less than or equal to h, we can try a smaller value of k. Otherwise, we need to try a larger value of k.

def minEatingSpeed(piles, h):
    left, right = 1, max(piles)
    ans = right

    while left <= right:
        k = (left + right) // 2
        hours = 0
        for pile in piles:
            hours += (pile + k - 1) // k

        if hours <= h:
            ans = k
            right = k - 1
        else:
            left = k + 1

    return ans

Example:

piles = [3, 6, 7, 11]
h = 8

minEatingSpeed(piles, h)  # Output: 4

3. Big(O) Run-time Analysis

The time complexity of the binary search approach is O(n * log(m)), where n is the number of piles and m is the maximum number of bananas in a pile. This is because we perform a binary search on the range of possible values for k, and for each value of k, we iterate through all the piles to calculate the number of hours it takes Koko to eat all the bananas.

4. Big(O) Space Usage Analysis

The space complexity of the binary search approach is O(1), as we only use a constant amount of extra space.

5. Edge Cases

• Empty piles: If the input list piles is empty, we should return 0. However, the problem statement says 1 <= piles.length <= 10^4, so we don't need to handle this case.
• h is smaller than the number of piles: The problem statement says piles.length <= h <= 10^9. If h is smaller than the number of piles, it is impossible for Koko to eat all the bananas within h hours. However, this condition is guaranteed to be false, so we don't need to handle this case.
• piles[i] is 0: The problem states that 1 <= piles[i] <= 10^9, so this edge case cannot happen.