Koko Eating Bananas

medium LeetCode #875
array binary-search

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
Explanation: With speed k=4:
- Pile 3: ceil(3/4) = 1 hour
- Pile 6: ceil(6/4) = 2 hours
- Pile 7: ceil(7/4) = 2 hours
- Pile 11: ceil(11/4) = 3 hours
Total = 1+2+2+3 = 8 hours <= 8 ✓
With k=3, total would be 1+2+3+4 = 10 hours > 8 ✗

Example 2:
Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: With h=5 and 5 piles, Koko has exactly 1 hour per pile. She must eat the largest pile (30) in 1 hour, so k=30.

Example 3:
Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Explanation: With k=23:
- Pile 30: ceil(30/23) = 2 hours
- Pile 11: ceil(11/23) = 1 hour
- Pile 23: ceil(23/23) = 1 hour
- Pile 4: ceil(4/23) = 1 hour
- Pile 20: ceil(20/23) = 1 hour
Total = 2+1+1+1+1 = 6 hours <= 6 ✓

Constraints

  • 1 <= piles.length <= 10^4
  • piles.length <= h <= 10^9
  • 1 <= piles[i] <= 10^9

Complexity

Show Complexity
  • Time: O(n log m)
  • Space: O(1)

Hints

Show Hints
Pattern
Binary search on answer space
Approach
The answer k is in range [1, max(piles)]. For each candidate k, calculate total hours needed: sum(ceil(pile/k)) for all piles. Binary search for minimum k where total <= h.
Complexity
Binary search on k from 1 to max(piles), check if valid in O(n)

Solutions

Show PY Solution 
import math


def solution(piles: list[int], h: int) -> int:
    # piles = [3, 6, 7, 11]
    # h = 8
    # if pile < k:
    #     eat all
    #
    # speed = h/piles[i]

    n = len(piles)
    s = sum(piles)
    left = math.ceil(s / h)
    right = math.ceil(s / (h - n + 1))
    # left = 1
    # right = max(piles)
    while left <= right:
        mid = left + (right - left) // 2

        sums = 0
        for p in piles:
            sums += math.ceil(p / mid)
            if sums > h:
                break

        # print(mid, sums, math.floor(sums / mid), h)

        if sums > h:
            left = mid + 1
        else:
            right = mid - 1

    return left

    # Brute force
    # for k in range(1, 100000000000):
    #     sums = 0
    #     for i in range(len(piles)):
    #         sums += piles[i]
    #     if sums // k <= h:
    #         return k