Koko Eating Bananas

MEDIUM✓ CHIP-TIMEDLC #875 — FULL STATEMENT ↗

The drill: Find the slowest whole-bananas-per-hour eating speed that still clears every pile within h hours — each hour is spent on one pile only, and a pile finished early wastes the rest of that hour.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Koko faces a row of banana piles and a fixed number of hours before the guards return; she picks one eating speed, in whole bananas per hour, and sticks with it for the entire ordeal.

Each hour she commits to a single pile: if the pile has fewer bananas than her speed, she finishes it early and the leftover time in that hour is wasted rather than carried to the next pile.

The job is to find the smallest whole-number speed that still lets her clear every pile within the hour budget — slower is kinder to the bananas but risks running out of time.

EX 01

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

→ 4

MIXED PILE SIZES

EX 02

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

→ 30

H EQUALS PILE COUNT, FORCES MAX SPEED

EX 03

piles = [30, 11, 23, 4, 20] · h = 6

→ 23

ONE EXTRA HOUR LOWERS THE SPEED

piles list holds up to a few thousand piles, each with a positive banana count
hour budget is always at least as large as the number of piles
eating speed must be a positive whole number, never zero or fractional
an hour spent on a nearly empty pile still costs the full hour

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Faster speeds always finish in fewer or equal hours than slower ones — hours-to-finish is monotonic in speed, which is exactly what makes bisecting the speed itself work.

HINT 2 THE STRUCTURE

For a candidate speed, the hours needed is the sum of ceil(pile / speed) over every pile — compute that directly instead of simulating hour by hour.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search speed in [1, max(piles)]: if the hours needed at mid exceeds h, mid is too slow — raise it; otherwise it's fast enough — try to go slower.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BANANA PACEPATTERN · BINARY SEARCH THE SPEEDpiles = [3, 6, 7, 11] · h = 8

HOURS NEEDED AT THIS SPEED

— empty —

STEP 1

4 piles: 3, 6, 7, 11 bananas. Binary-search Koko's speed in [1, 11] — the biggest pile — for the slowest speed that clears them in 8 hours.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/koko-eating-bananas.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            hours = sum((p + mid - 1) // mid for p in piles)
            if hours <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo

TIME O(N LOG(MAX(PILES)))SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        speed = 1
        while True:
            hours = sum((p + speed - 1) // speed for p in piles)
            if hours <= h:
                return speed
            speed += 1

TIME O(MAX(PILES) · N)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int p : piles) {
            hi = Math.max(hi, p);
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long hours = 0;
            for (int p : piles) {
                hours += (p + mid - 1) / mid;
            }
            if (hours <= h) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

TIME O(N LOG(MAX(PILES)))SPACE O(1)JAVA · RACE PACE · 21 LN

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int speed = 1;
        while (true) {
            long hours = 0;
            for (int p : piles) {
                hours += (p + speed - 1) / speed;
            }
            if (hours <= h) {
                return speed;
            }
            speed++;
        }
    }
}

TIME O(MAX(PILES) · N)SPACE O(1)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED