Koko Eating Bananas

The problem

Koko has several piles of bananas and h hours to eat them. She picks one eating speed, a whole number of bananas per hour, and keeps it. Each hour she eats from a single pile: that many bananas, or the whole pile if it is smaller. Return the smallest speed that finishes every pile within h hours.

What to write

function solve(piles: number[], h: number): number

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

Output
4

Input
piles = [30,11,23,4,20]
h = 5

Output
30

Constraints

piles.length ≤ h; piles contain positive integers.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The answer is a speed between 1 and the largest pile. Faster than that gains nothing, because she eats from one pile per hour.

2. Hint 2: Ask a smaller question

   Forget "smallest" for a moment. Given one speed, can you work out whether it finishes in time?

3. Hint 3: Name the pattern

   If a speed is fast enough, every faster speed is too. So the speeds are a run of "too slow" followed by a run of "fast enough", and you want the first "fast enough". That is binary search on the answer. Read the lesson on binary search on the answer.

4. Hint 4: State the invariant

   Keep a range of speeds that always contains the answer. A speed that works might be the answer, so keep it. A speed that fails cannot be, so drop it.

5. Hint 5: Sketch the pseudocode

   low = 1, high = largest pile. While low < high: take the middle speed, mid, rounded down, and add up the hours, rounding each pile up. In time: high = mid. Too slow: low = mid + 1. Return low.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Binary-search eating speed because feasibility is monotonic: a speed that works implies every faster speed works.

The slow way

Try speed 1, then 2, then 3, and return the first one that finishes in time. It is correct, but it can test every speed up to the largest pile, and each test walks every pile.

The insight

"Does this speed finish in time?" can go from no to yes as the speed grows, but never from yes back to no. So one test in the middle tells you which half of the remaining speeds to throw away.

Step by step

1. The answer is somewhere from 1 to the largest pile. At the largest pile's size every pile takes one hour, and there are at least as many hours as piles, so that speed always works.
2. Try the middle speed and count the hours it needs. A pile takes its size divided by the speed, rounded up, because a started hour is a used hour.
3. Fast enough: the answer is this speed or a slower one. A speed that works might still be the smallest one, so it stays in the range.
4. Too slow: the answer is a faster speed. A speed that fails can never be the answer, so it leaves the range together with everything slower.
5. One speed is left: that is the answer. The range always held the answer and shrank every round, so the last speed standing is it.

The same numbered steps are the comments in each solution.

function solve(piles, h) {
  // 1. The answer is somewhere from 1 to the largest pile
  let l = 1,
    r = Math.max(...piles);
  while (l < r) {
    // 2. Try the middle speed and count the hours it needs
    const m = Math.floor((l + r) / 2);
    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / m), 0);
    if (hours <= h) {
      // 3. Fast enough: the answer is this speed or a slower one
      r = m;
    } else {
      // 4. Too slow: the answer is a faster speed
      l = m + 1;
    }
  }
  // 5. One speed is left: that is the answer
  return l;
}

function solve(piles: number[], h: number): number {
  // 1. The answer is somewhere from 1 to the largest pile
  let l = 1,
    r = Math.max(...piles);
  while (l < r) {
    // 2. Try the middle speed and count the hours it needs
    const m = Math.floor((l + r) / 2);
    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / m), 0);
    if (hours <= h) {
      // 3. Fast enough: the answer is this speed or a slower one
      r = m;
    } else {
      // 4. Too slow: the answer is a faster speed
      l = m + 1;
    }
  }
  // 5. One speed is left: that is the answer
  return l;
}

import math


def solve(piles, h):
    # 1. The answer is somewhere from 1 to the largest pile
    left, right = 1, max(piles)
    while left < right:
        # 2. Try the middle speed and count the hours it needs
        mid = (left + right) // 2
        hours = sum(math.ceil(pile / mid) for pile in piles)
        if hours <= h:
            # 3. Fast enough: the answer is this speed or a slower one
            right = mid
        else:
            # 4. Too slow: the answer is a faster speed
            left = mid + 1
    # 5. One speed is left: that is the answer
    return left

Example 1, traced

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

Output
4

Why it works

The range always contains the smallest speed that works: a working speed is kept, and a failing one is dropped along with everything slower. Each round removes at least one speed, so the loop ends on exactly that speed.

Time and space

Time O(n log max(piles)), extra space O(1). Each test walks all n piles. The range starts as wide as the largest pile and halves every round, so the number of tests is the logarithm of the largest pile. Only a few numbers are stored.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Round up when you divide: a pile of 7 at speed 3 takes 3 hours, not 2.
• When a speed works, keep it in the range. Moving past it can throw the answer away.

Pattern

Binary search on the answer. Builds on Binary Search.

Keep going