Koko Eating Bananas Problem

Problem Description

Koko loves to eat 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 can decide her bananas-per-hour eating speed, 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 wants to eat slowly but 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.

Naive Approach

The most straightforward approach is to iterate through all possible values of k from 1 to the maximum number of bananas in any pile. For each k, we calculate the total time it takes Koko to eat all the bananas. If the total time is less than or equal to h, we have found a valid k. We continue searching for a smaller k to minimize the eating speed.

Code (Python)

def can_eat_all(piles, h, k):
    time = 0
    for pile in piles:
        time += (pile + k - 1) // k  # Ceiling division
    return time <= h

def min_eating_speed_naive(piles, h):
    max_pile = max(piles)
    for k in range(1, max_pile + 1):
        if can_eat_all(piles, h, k):
            return k
    return max_pile  # In case no solution is found

Time Complexity

O(m * n), where m is the maximum number of bananas in a pile, and n is the number of piles. This is because we iterate through all possible values of k up to the largest pile size, and for each k, we iterate through all the piles.

Space Complexity

O(1), as we use only a constant amount of extra space.

Optimal Approach: Binary Search

Since we are looking for the minimum value of k that satisfies a condition, we can use binary search. The possible range for k is between 1 and the maximum number of bananas in any pile.

We perform binary search within this range. For each mid-value k, we check if Koko can eat all the bananas within h hours. If she can, we try to find a smaller k by searching in the lower half. Otherwise, we search in the upper half.

Code (Python)

def can_eat_all(piles, h, k):
    time = 0
    for pile in piles:
        time += (pile + k - 1) // k  # Ceiling division
    return time <= h

def min_eating_speed(piles, h):
    left, right = 1, max(piles)
    ans = right
    while left <= right:
        mid = (left + right) // 2
        if can_eat_all(piles, h, mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

Time Complexity

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 binary search, which takes O(log(m)) iterations, and in each iteration, we iterate through all the piles, which takes O(n) time.

Space Complexity

O(1), as we use only a constant amount of extra space.

Edge Cases

• Empty input: If piles is empty, return 0 or raise an exception, depending on the requirements.
• h is very small: If h is smaller than the number of piles, it is impossible for Koko to eat all the bananas. In this case, return an appropriate error value or raise an exception.
• h is very large: If h is sufficiently large (e.g., greater than or equal to the sum of the reciprocals of the pile sizes), the solution would be 1. However, the binary search approach handles this automatically.
• Large pile sizes: The pile sizes can be up to 10^9. Ensure that intermediate calculations (e.g., in can_eat_all) do not overflow.