Koko Eating Bananas

Q: What is the time complexity of Koko Eating Bananas?

The binary search runs in O(n log m) time, where n is the number of piles and m the largest pile: about log2(m) checks, 30 when m = 10^9 , each reading every pile once. The extra space is O(1) .

Q: What are the lower and upper bounds for the speed?

The upper bound is the largest pile: there every pile takes one hour, which always fits. The lower bound is 1, and you can raise it to the total number of bananas divided by h , rounded up, because Koko eats at most k bananas an hour.

Q: How do you divide and round up with integers?

Use (p + k-1) / k with integer division. Adding k-1 pushes any remainder past the next multiple of k , and an exact multiple stays put: 10 at speed 4 gives 13 / 4 = 3 , and 8 gives 11 / 4 = 2 . No floating point is needed.

MediumBinary search

+10

Koko has n piles of bananas, with piles[i] bananas in pile i, and h hours. She picks one eating speed k, a whole number of bananas per hour, and keeps it. Each hour she eats k bananas from one pile; if that pile has fewer than k left, she finishes it and rests until the hour is over. Return the smallest k that lets her finish every pile within h hours.

Function

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: the number of bananas in each pile
hinteger: the number of hours Koko has
Returnsinteger: the smallest whole eating speed, in bananas per hour, that finishes every pile within h hours

Constraints

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, so an answer always exists.

Examples

Input: piles = [4, 10, 7, 3]h = 6
Output: 5
Explanation: At speed 5 the piles 4, 10, 7 and 3 take 1, 2, 2 and 1 hours: 6 in total, which fits. At speed 4 they take 1, 3, 2 and 1, which is 7.

Follow-up

Twin problem: Koko eats whole piles in order, at most k bananas a day, within d days. What is the smallest k, and what changes in your search?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The answer is a speed, not a position in the array, and that hides a binary search. Checking one speed takes one pass over the piles, and if speed k finishes in time, every faster speed does too. So binary search the speeds from 1 to the largest pile: about 30 checks instead of up to a billion.

Try every speed from 1 upward

Correct, but does not finish on the largest tests

Intuition

Koko never moves to another pile inside an hour, so a pile of p bananas takes p / k hours rounded up: 10 at speed 4 takes 3 hours. Try speeds 1, 2, 3 and so on, and return the first whose total fits in h. It is the smallest because every slower speed failed, and the loop stops by the largest pile's speed, where each pile takes one hour.

With m the largest pile, that is up to m checks of n piles: about 5 × 10^12 steps for 5000 piles near 10^9 and h = 5000.

Algorithm

Set speed = 1.
Count the hours at this speed: for each pile add (pile + speed-1) / speed, using a 64-bit total.
If the total is at most h, return speed.
Otherwise add 1 to speed and count again.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Binary search on the speed

Intuition

As the speed grows, each pile takes the same number of hours or fewer, so the answers to "does this speed finish in time?" read no, no, no, then yes from the answer onward. Binary search finds that first yes.

Keep a range lo to hi that always holds the answer, starting at 1 and the largest pile, whose speed takes one hour per pile and so fits. If the middle speed mid fits, the answer is mid or slower, so set hi = mid. If not, every slower speed fails too, so set lo = mid + 1. When lo meets hi, that is the answer.

In the first example the range starts at 1 to 10. Speed 5 fits, so it becomes 1 to 5; speed 3 takes 10 hours, so 4 to 5; speed 4 takes 7, so 5 to 5.

Algorithm

Set lo = 1 and hi to the largest pile.
While lo < hi, take mid = lo + (hi - lo) / 2.
Count the hours at speed mid: add (pile + mid-1) / mid for every pile, in a 64-bit total.
If the total is at most h, set hi = mid; otherwise set lo = mid + 1.
Return lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Pitfalls and edge cases

Overflowing the hour count. At speed 1, 5000 piles of 10^9 bananas take 5 × 10^12 hours, past the 32-bit limit, and a wrapped total can let a slow speed pass. Count in 64 bits, or stop once the total passes h.
Rounding down. 10 / 4 gives 2, yet that pile takes 3 hours.
Starting the range at 0. Then mid can be 0 and the count divides by zero.
Setting hi = mid - 1 when mid fits. That can discard the answer.
Starting hi below the largest pile. When h equals the number of piles, every lower speed fails, and the search returns one of them.

Frequently asked questions3

What is the time complexity of Koko Eating Bananas?

The binary search runs in O(n log m) time, where n is the number of piles and m the largest pile: about log2(m) checks, 30 when m = 10^9, each reading every pile once. The extra space is O(1).

What are the lower and upper bounds for the speed?

The upper bound is the largest pile: there every pile takes one hour, which always fits. The lower bound is 1, and you can raise it to the total number of bananas divided by h, rounded up, because Koko eats at most k bananas an hour.

How do you divide and round up with integers?

Use (p + k-1) / k with integer division. Adding k-1 pushes any remainder past the next multiple of k, and an exact multiple stays put: 10 at speed 4 gives 13 / 4 = 3, and 8 gives 11 / 4 = 2. No floating point is needed.

def minEatingSpeed(piles, h):
    # Write code here

Test #1

Test #2

Test #3

Arguments

piles = [4, 10, 7, 3]
h = 6

Expected Output