Workspace

Problem workspace

3 day streakD

Koko Eating Bananas

MediumBinary SearchSearch on the answer

The challenge

Find the smallest integer speed allowing all piles to be eaten in at most h hours. Each hour is spent on one pile.

Nonempty positive integer piles, each ≤ 10⁹. Return −1 when h < number of piles. Sums of counts fit 64-bit integers.

Example

[3, 6, 7, 11], h = 8 → speed 4, needing 1 + 2 + 2 + 3 hours.

Use the walkthrough below to inspect the input and each state change.

See Minimum feasible speed, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchh = 8
left1candidate—right11Search candidate values, not input indices
306172113
Tested candidate / qualifying inputResolved positionParameters shown above
Left
1
Middle
—
Right
11
Step 01 / 6

Search the answer range

The candidate is a number, rather than an input index. Keep the smallest feasible value.

left = 1; right = 11

Recorded result so far

Not resolved
View exact input

Input: [3,6,7,11] · h = 8

Put it into code

The hours needed never increase as speed rises. Search the first speed whose total ceiling-divided hours is within budget.

Indices are zero-based. C++ uses C++17 or later.

def minimum_speed(piles, h):
    # Nonempty positive piles; h >= 0. One pile per hour.
    if h < len(piles):
        return -1
    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        hours = sum((pile + mid - 1) // mid for pile in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap