DSA Koko Eating Bananas (Answer-Space Search)

The problem

Koko Eating Bananas asks for the slowest eating speed that finishes every pile within a limit of hours. Koko eats from one pile per hour, at a fixed number of bananas per hour, and a partly eaten pile still costs its full hour.

The speed is a whole number of bananas per hour. The answer is the smallest speed whose total hours fit the limit. A speed equal to the largest pile always works when the limit is at least the number of piles.

cases = [
    ([3, 6, 7, 11], 8, 4),
    ([30, 11, 23, 4, 20], 6, 23),
    ([30, 11, 23, 4, 20], 5, 30),
    ([1, 1, 1], 3, 1),
    ([5], 1, 5),
]
for piles, limit, expected in cases:
    print("piles", piles, "limit", limit, "slowest speed:", expected)

Read one row at a time. The third row allows one hour per pile, so the speed must clear the largest pile in a single hour. The last row makes the same point with one pile.

Intuition: dividing the total by the limit ignores the rounding

The first idea adds all the bananas and divides by the hour limit. That gives a fair average speed. It feels like the natural answer.

The average ignores one rule. Each pile rounds its hours up on its own, and a new pile never shares the leftover room in an hour. The average speed below fails its own limit.

piles = [3, 6, 7, 11]
limit = 8
speed = sum(piles) // limit
hours = 0
for pile in piles:
    share = (pile + speed - 1) // speed
    hours += share
    print("pile:", pile, "hours at speed", speed, ":", share)
print("average speed:", speed, "total hours:", hours, "limit:", limit, "works:", hours <= limit)

Speed 3 needs 10 hours against a limit of 8. Four separate roundings added the extra hours. Any correct method must price each pile on its own.

Brute force: test speeds from 1 upward

The brute force tests speed 1, then 2, then 3, and stops at the first speed that fits the limit. Each test prices every pile with the rounded-up share. A counter records the speeds tested.

The rounded-up share for one pile is pile plus speed minus 1, divided by speed with whole-number division. That formula needs no fractions. It gives 1 hour for any pile at or under the speed.

def hours_for(piles, speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total

def min_speed_brute(piles, limit):
    speed = 1
    tested = 0
    while True:
        tested += 1
        if hours_for(piles, speed) <= limit:
            return speed, tested
        speed += 1

speed, tested = min_speed_brute([3, 6, 7, 11], 8)
print("slowest speed:", speed, "speeds tested:", tested)
speed, tested = min_speed_brute([30, 11, 23, 4, 20], 5)
print("slowest speed:", speed, "speeds tested:", tested)

The second row tested 30 speeds, one per value up to the answer. Each test walked all five piles. A large largest pile makes the upward walk long.

The optimal solution: binary search the answer itself

The check for one speed is a predicate, a test that answers yes or no, and it is monotone, meaning a yes stays yes for every larger speed, so binary search over the speeds finds the first yes. That one sentence is the whole method.

This is answer-space search, the search of the answer itself rather than of the data. The range runs from 1 up to the largest pile. A working middle speed moves the right edge to the middle, and a failing one moves the left edge past it.

def hours_for(piles, speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total


def min_speed(piles, limit):
    lo = 1
    hi = max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_for(piles, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

cases = [
    ([3, 6, 7, 11], 8, 4),
    ([30, 11, 23, 4, 20], 6, 23),
    ([30, 11, 23, 4, 20], 5, 30),
    ([1, 1, 1], 3, 1),
    ([5], 1, 5),
]
for piles, limit, expected in cases:
    result = min_speed(piles, limit)
    print("piles", piles, "limit", limit, "->", result, "expected:", expected, "match:", result == expected)

All five cases from the start of the article pass. The first-yes position is the answer in each row. Speeds below it fail and speeds at or above it pass.

Walkthrough: piles of 3, 6, 7 and 11 with a limit of 8

The walk halves the speed range from 1 to 11. The state is the range and the verdict on its middle speed. Each line prices the guess pile by pile through the total.

def hours_for(piles, speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total

piles = [3, 6, 7, 11]
limit = 8
lo = 1
hi = max(piles)
while lo < hi:
    mid = (lo + hi) // 2
    hours = hours_for(piles, mid)
    works = hours <= limit
    print("range", lo, hi, "- guess", mid, "hours:", hours, "works:", works)
    if works:
        hi = mid
    else:
        lo = mid + 1
print("slowest working speed:", lo)

The guesses run 6, 3, 5 and 4. The failing guess at 3 pushes the range up, and the passing guesses pull the right edge down. The range closes on 4, the first speed that passes.

Complexity

The brute force tests up to the largest pile in speeds, and each test prices every pile, so its time is O(largest pile times pile count). Answer-space search tests about log of the largest pile in speeds, so its time is O(log of the largest pile, times pile count).

Both methods store only totals and range edges beyond the input list. Their extra space is O(1).

def hours_for(piles, speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total

def binary_guesses(piles, limit):
    lo = 1
    hi = max(piles)
    guesses = 0
    while lo < hi:
        mid = (lo + hi) // 2
        guesses += 1
        if hours_for(piles, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo, guesses

def brute_guesses(piles, limit):
    speed = 1
    while hours_for(piles, speed) > limit:
        speed += 1
    return speed, speed

for piles, limit in [([3, 6, 7, 11], 8), ([30, 11, 23, 4, 20], 5), ([100, 90, 80], 3)]:
    answer_b, count_b = brute_guesses(piles, limit)
    answer_s, count_s = binary_guesses(piles, limit)
    print("largest pile", max(piles), "- brute speeds tested:", count_b, " search guesses:", count_s, " answer:", answer_s)

Counts beat clocks here. At a largest pile of 100 the upward walk tests 100 speeds. The search answers in 6 guesses, with the same result.

Edge cases and pitfalls

Speed zero is not a slow option, it is a broken one. It divides by zero in the share formula. The search range starts at 1, so zero is never tested.

A limit equal to the pile count forces one hour per pile. The answer is then the largest pile. A generous limit drops the answer to 1, because even the slowest real speed finishes in time.

def hours_for(piles, speed):
    total = 0
    for pile in piles:
        total += (pile + speed - 1) // speed
    return total


def min_speed(piles, limit):
    lo = 1
    hi = max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_for(piles, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

print("one pile, one hour:", min_speed([5], 1))
print("one pile, five hours:", min_speed([5], 5))
print("limit equals pile count:", min_speed([30, 11, 23, 4, 20], 5))
print("generous limit:", min_speed([3, 6, 7, 11], 100))
print("hours at speed 1:", hours_for([3, 6], 1))
print("tiny pile at a fast speed:", hours_for([2], 9))

The last row still costs a full hour. A pile never shares an hour with another pile, at any speed. That single rule is what broke the average-speed idea at the start.