DSA Factory
Free Binary search lessonsBinary search · Stage 2 · Search on the answer · Step 1

Guess the answer, then check it

Find the smallest speed that finishes the job in time, by halving the range of possible speeds. About 15 minutes.

A check that only goes one way

A monkey has piles of bananas and must finish them all within a number of hours. Each hour it picks one pile and eats up to its speed from it. If a pile has fewer left, the monkey wastes the rest of that hour. What is the smallest speed that finishes in time?

Checking a given speed is easy: add up how many hours each pile takes, rounding up. And a faster speed never takes more hours. That one-way behaviour is what lets you halve.

Check: hours needed at a speed, rounding each pile up.
Faster never hurts: so the speeds are no, no, yes, yes.
In code
def hours_needed(speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total
Piles 3, 6, 7, 11 and 8 hours. Candidate speeds 1 to 11.
1
0
2
1
3
2
4
3
5
4
6
5
7
6
8
7
9
8
10
9
11
10
leftright

Any speed from 1 to 11 might be the answer. Try the middle, speed 6.

Move 1 of 5

Halve the range

The smallest possible speed is 1 and the largest worth trying is the biggest pile, since faster than that gains nothing. Look at the middle speed. If it finishes in time, the answer is that speed or something smaller, so keep the lower half including mid. If not, the answer is bigger, so move past mid.

Stop when the range is a single speed. That speed is the first yes.

Works: keep mid; the answer is mid or lower.
Too slow: drop mid; the answer is higher.
In code
low, high = 1, max(piles)
while low < high:
    mid = (low + high) // 2
    if hours_needed(mid) <= hours:
        high = mid
    else:
        low = mid + 1
return low
Quick check

A speed of 7 finishes in time. What does that tell you about a speed of 9?

  1. A9 also finishes in time, since faster is never slower
  2. B9 might fail
  3. CYou have to test 9 to know
Show the answer

9 also finishes in time, since faster is never slower. The check is one-way, so every speed above a working speed works too.

Your problem

Smallest eating speed

piles[i] is the number of bananas in pile i. A monkey must finish all the piles within hours hours. Each hour it chooses one pile and eats up to k bananas from it; if the pile has fewer than k, it eats them all and does nothing else that hour. Return the smallest whole k that lets the monkey finish in time. It is guaranteed that hours is at least the number of piles.

Example
piles = [3, 6, 7, 11], hours = 8 → 4

1 ≤ piles ≤ 100,000 · 1 ≤ pile ≤ 1,000,000,000 · piles ≤ hours ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve