Koko Eating Bananas

Updated on 05 June, 2025
Koko Eating Bananas header image

Problem Statement

Koko loves to eat bananas and has a unique way of doing so. She has access to n piles of bananas where each pile contains a specific number of bananas denoted by piles[i]. Koko has a limited time, as the guards who watch over the bananas will return in h hours. She can set her own pace by choosing a rate k, which represents how many bananas she can eat per hour. When Koko eats, she focuses on one pile per hour, consuming k bananas from it. If a pile contains fewer than k bananas, she will finish that pile and wait until the next hour to continue. Koko's challenge is to determine the minimal eating speed k that allows her to consume all bananas across all piles within the time before the guards return.

Examples

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

Approach and Intuition

To solve the problem of finding the minimum eating speed k for Koko, we need to grasp the relationship between k and the total time T taken to consume all the bananas:

  1. Initial Observations:

    • If k is very large (i.e., at least equal to the largest pile), Koko can finish the bananas in each pile in roughly one hour per pile or even less.
    • If k is very small, the number of hours required to finish all bananas increases significantly.
  2. Understanding the relationship:

    • For a given k, the total hours T needed is the sum of the hours required for each pile, which is calculated as the ceiling of the division of pile size by k (i.e., each pile piles[i] requires (piles[i] + k - 1) // k hours).
  3. Binary Search for Efficiency:

    • Given the constraints and the nature of the problem (searching for a minimum k that allows completing all piles within h hours), a binary search approach is ideal.
    • Set initial boundaries for k: the lower bound can be 1 (minimum possible speed), and the upper bound can be set to the maximum number in piles (maximum speed required if Koko decides to eat the largest pile in one hour).
    • We use a conditional loop to narrow down the value of k. In each iteration, choose the middle value of k, calculate the resultant hours T for this k, and adjust the bounds:
      • If T is less than or equal to h, it means k might be optimized further; thus, reduce the upper bound.
      • If T is greater than h, increase the lower bound to explore higher values of k for feasibility.
  4. Finalizing the result:

    • The iterative refinement via binary search will converge when the lower and upper bounds meet, resulting in the smallest k that allows Koko to finish all the bananas within the allotted h hours.

This approach efficiently handles the large possible range of values due to the constraints and directly addresses the question of the minimal satisfactory k.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp
class Solution {
public:
    int findMinSpeed(vector<int>& piles, int H) {
        int low = 1, high = *max_element(piles.begin(), piles.end());

        while (low < high) {
            int mid = (low + high) / 2;
            int totalHours = 0;

            for (int bananas : piles) {
                totalHours += bananas / mid + (bananas % mid != 0);
            }

            if (totalHours <= H) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }
};

In the given C++ code, the solution focuses on solving the problem where Koko can eat bananas at a variable rate but must finish all the bananas within a set number of hours, H. The essence of the solution leverages a binary search approach to efficiently find the minimum integer rate at which Koko should eat the bananas to achieve this goal.

Here's a breakdown of how the solution works:

  • Start by setting the initial search range for the eating rate (low to high). The low is set to 1 (minimum possible eating rate) and high is set to the maximum number of bananas in any pile using the max_element function. This ensures the rate is logically bounded by the maximum pile size, as Koko cannot eat faster than the size of the largest pile per hour.

  • Execute a binary search:

    • Calculate a mid-point rate (mid) to test.
    • For each pile of bananas, compute how many hours it would take for Koko to eat that pile at the mid rate, rounding up to ensure each pile is fully eaten.
    • Sum these hours across all piles.
  • Determine if the computed total hours fit within the allowed hours (H):

    • If Koko can finish within H hours at the mid rate, search for a potentially lower rate by adjusting high to mid.
    • If more hours are needed, adjust low to mid + 1 to try a faster eating rate.
  • The search concludes when the low meets high, at which point low will represent the minimal eating rate that allows Koko to finish all the bananas within H hours.

By the conclusion of this code execution, you obtain the minimized eating rate as a result, enabling efficient completion of the task within the set constraints.

java
class Solution {
    public int minimumEatingSpeed(int[] piles, int hours) {
        int minSpeed = 1, maxSpeed = 1;
        for (int pile : piles) {
            maxSpeed = Math.max(maxSpeed, pile);
        }

        while (minSpeed < maxSpeed) {
            int mid = (minSpeed + maxSpeed) / 2;
            int totalHours = 0;
            for (int pile : piles) {
                totalHours += Math.ceil((double) pile / mid);
            }

            if (totalHours <= hours) {
                maxSpeed = mid;
            } else {
                minSpeed = mid + 1;
            }
        }

        return maxSpeed;
    }
}

The Java code provided solves the problem of determining the minimum eating speed at which Koko can eat all the bananas within the given hours. The code uses a binary search approach. This method efficiently narrows down the speed range until it finds the minimum speed that allows Koko to finish the bananas in time.

  • The minimumEatingSpeed function takes two parameters: an array piles of banana counts and an integer hours for the maximum allowed time.
  • Initialize minSpeed to 1 and maxSpeed to the maximum element in piles found using a loop, as Koko cannot eat at a speed slower than 1 or faster than the largest pile per hour.
  • Execute a binary search between minSpeed and maxSpeed:
    • Calculate the mid-point mid representing a potential eating speed.
    • Calculate total hours required to eat all piles at this speed. Round up the division result for each pile to consider partial hours as full hours.
    • If totalHours is less than or equal to hours, adjust maxSpeed to mid because a lower or equal speed might also be a valid solution.
    • Otherwise, increase minSpeed to mid + 1 to look for a faster valid speed as the current one is too slow.
  • When the loop terminates, maxSpeed holds the minimum speed at which Koko can eat all the bananas within the given hours.

This approach optimally balances between too high and too low speeds and ensures that the solution is both correct and efficient, typically achieving O(n log m) complexity, where n is the number of piles, and m is the range of possible speeds.

js
var minimumEatingSpeed = function(bananas, maxHours) {
    let low = 1, high = 1;
    for (const banana of bananas) {
        high = Math.max(high, banana);
    }

    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        let totalHours = 0;

        for (const banana of bananas) {
            totalHours += Math.ceil(banana / mid);
        }

        if (totalHours <= maxHours) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return low;
}

The code provided defines a function in JavaScript intended to solve the problem of finding the minimum speed at which Koko must eat bananas in order to consume all bananas within a given maximum number of hours. This problem context involves figuring out an optimal eating rate given constraints on time and quantity.

  • In the function minimumEatingSpeed, two parameters are expected: bananas, an array where each element represents the number of bananas in a pile, and maxHours, which depicts the maximum hours Koko has to eat all the bananas.
  • To find the solution, the function employs a binary search technique. It initializes two variables, low and high. low starts at 1 (since the minimum possible eating speed is at least one banana per hour), and high is set initially to the maximum number of bananas in any pile, ensuring the search boundary encompasses all possible eating speeds from slowest to fastest required.

The main logic:

  1. A loop computes the values for high to ensure it captures the largest pile count from the bananas array using Math.max.
  2. Through the while loop, the binary search continues until low is less than high.
  3. Within this loop, mid represents the middle value between low and high, suggesting a potential answer for the minimum eating speed.
  4. Another loop calculates totalHours by iterating through every pile; it calculates the hours it would take for Koko to eat each pile at mid speed using Math.ceil to account for partial hours.
  5. Decision-making inside the while loop adjusts the bounds (low and high) based on whether the calculated totalHours with the current mid value is within the allowable maxHours.
  6. If Koko can finish the bananas in fewer or equal hours than maxHours, reduce the upper boundary (high = mid), otherwise increase the lower boundary (low = mid + 1).

At the end of the binary search, low holds the minimum speed at which Koko must eat the bananas to meet the time constraint, and this value is returned by the function. This approach efficiently handles the constraints and finds an optimal rate using a time complexity typically logarithmic relative to the initial high value setup, providing a quick and scalable solution.

python
class Solution:
    def findMinSpeed(self, piles: List[int], hours: int) -> int:
        # Define search range
        low = 1
        high = max(piles)

        # Using binary search to find the optimal speed
        while low < high:
            mid = (low + high) // 2
            total_hours = 0

            # Calculate total hours taken to finish all piles with current speed
            for pile in piles:
                total_hours += math.ceil(pile / mid)

            # Narrow down the search range based on the number of hours
            if total_hours <= hours:
                high = mid
            else:
                low = mid + 1

        # low or high is the answer
        return low

In the provided Python solution, the goal is to determine the minimum eating speed at which Koko can eat all the banana piles within a given number of hours. The function findMinSpeed employs a binary search mechanism to efficiently find this speed.

Here's how the solution works:

  • Begin by defining the range for Koko's possible eating speeds. This ranges from 1 to the maximum number of bananas in any pile since Koko must eat at least one banana per hour and cannot eat faster than the size of the largest pile per hour.

  • The search for the optimal speed is a classic binary search where:

    • Calculate the middle of the current range (mid) as the potential eating speed.
    • Compute the total hours required to eat all piles at this speed. For each pile, use the ceiling of the division of pile size by current mid (i.e., math.ceil(pile / mid)), which ensures that partial bananas still require a full hour to complete.
  • Adjust the search range based on whether the computed total hours exceed the allowed hours:

    • If the total hours needed are less than or equal to the allowed hours, then reduce the upper boundary of the search range (high) to mid.
    • If the total hours exceed the allowed hours, increase the lower boundary of the search range (low) to mid + 1.
  • When low meets or exceeds high, the search concludes, and low is the minimum speed at which Koko can finish all the bananas within the allowed hours.

This search leverages the efficiency of binary search to find the solution in logarithmic time relative to the range of speeds, making it very efficient even for large inputs. The use of math.ceil ensures that the calculation accounts for partially eaten piles correctly for every hour.

Comments

No comments yet.