Search on the answer: capacity and speed

Search on the answer means binary searching the possible answers themselves instead of positions in the input. It fits questions of the form “what is the smallest speed, or the smallest capacity, that still finishes in time?”. Pick a guess, check it with one pass over the input, and use the verdict to discard half of the remaining guesses: if speed s finishes in time, every faster speed does too, and if it does not, no slower speed can. With answers up to 10⁹ that takes about 30 checks. What follows is an original version of the task widely called Koko eating bananas, a count of what the brute force would take at its limits, and the signal that points to this search.

The problem: the slowest speed that finishes the revision

1. pages = [12, 7, 30, 18] and h = 8 give 10: at 10 pages an hour the chapters take 2 + 1 + 3 + 2 = 8 hours, and at 9 they would take 9.
2. The same chapters with h = 4 give 30: one hour per chapter, so the speed must cover the longest chapter.
3. One chapter of 1,000,000,000 pages with h = 3 gives 333,333,334.

The brute force: try every speed

Try s = 1, 2, 3 and so on, add up the hours each speed needs, ⌈p / s⌉ for every chapter, and stop at the first speed that fits. Each try is one pass over the chapters, but the answer can be as large as 10⁹, so the tries can number 10⁹ and the work 10¹⁴:

"""The slowest reading speed, found by trying 1, 2, 3, ... pages an hour: the brute force, with its tries counted."""
import random
import time


def hours_needed(pages, speed):
    """Each hour goes to one chapter, so a chapter of p pages takes ceil(p / speed) hours."""
    return sum(-(-p // speed) for p in pages)


def slowest_by_trying(pages, h):
    speed = 1
    while hours_needed(pages, speed) > h:
        speed += 1
    return speed  # the speed is also the number of tries


for pages, h in [([12, 7, 30, 18], 8), ([12, 7, 30, 18], 4), ([1_000, 2_000], 3)]:
    speed = slowest_by_trying(pages, h)
    print(f"{pages}, h = {h}: speed {speed:,} after {speed:,} tries")

# One try at the limits: 100,000 chapters of up to a billion pages each.
rng = random.Random(2)
chapters = [rng.randint(1, 10**9) for _ in range(100_000)]
start = time.perf_counter()
for speed in (1, 1_000, 1_000_000):
    hours_needed(chapters, speed)
per_try = (time.perf_counter() - start) / 3
print(f"one try over 100,000 chapters: about {per_try * 1000:,.0f} ms")
print(f"an answer near 10^9 needs about 10^9 tries: about {per_try * 10**9 / 86_400 / 365:,.1f} years")

[12, 7, 30, 18], h = 8: speed 10 after 10 tries
[12, 7, 30, 18], h = 4: speed 30 after 30 tries
[1000, 2000], h = 3: speed 1,000 after 1,000 tries
one try over 100,000 chapters: about 7 ms
an answer near 10^9 needs about 10^9 tries: about 0.2 years

One try over 100,000 chapters takes milliseconds, and a billion of them would take months or years, where the time limit is a second or two.

What to notice

A faster speed never needs more hours: each chapter’s ⌈p / s⌉ can only fall or stay the same as s grows. So “finishes within h hours” is false for slow speeds and true from one speed on, a condition that flips once along the speeds 1 to 10⁹. Capacity behaves the same way: a bigger van never needs more days to carry the same parcels in the same order. The input does not need to be sorted or searched at all: the thing to search is the answer.

The slowest speed by halving, step by step Pro: opens with a Pro, Premium or Ultimate pass