algoadvance

Koko loves to eat bananas. There are n piles of bananas, 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 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 that 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:

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

Constraints:

Clarifying Questions

  1. Can Koko start eating from any pile at any hour?
    • Yes, in any hour she can start eating from any pile.
  2. What happens if k is so large that Koko finishes a pile in less than an hour?
    • If k is larger than the pile’s size, she finishes the pile and waits until the next hour to start a new pile.
  3. Can we assume the input is always valid and within constraints?
    • Yes.

Strategy

  1. Identify the Range for k:
    • The minimum speed k can be 1 (eating 1 banana per hour).
    • The maximum speed k can be the largest pile size (max(piles)) because if Koko eats all bananas from the largest pile in one hour, she will definitely have time for the rest.
  2. Binary Search Approach:
    • Use binary search to efficiently determine the lowest possible k that allows Koko to eat all bananas within h hours.
    • For each midpoint in this range, calculate the total hours required to eat all bananas using that speed.
    • Adjust the range based on whether the hours required are within the limit h.
  3. Details:
    • For a given k, calculate the total hours required:
      • For each pile, the hours required is (pile size // k) rounded up.
      • Sum these values for all piles.
    • If the sum of hours is less than or equal to h, adjust the range to search for a smaller k.
    • If greater, increase k.

Code

from math import ceil

def minEatingSpeed(piles, h):
    def canEatAllBananas(k):
        total_hours = 0
        for pile in piles:
            total_hours += ceil(pile / k)
        return total_hours <= h
    
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if canEatAllBananas(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

Time Complexity

  1. Binary Search:
    • The binary search will run in O(log(max(piles))) because we are halving the search range each time.
  2. Checking If K is Valid:
    • Summing the hours required for all piles takes O(n) time, where n is the number of piles.

Overall time complexity: O(n * log(max(piles))).

This complexity should be efficient enough given the problem constraints.

Try our interview co-pilot at AlgoAdvance.com