Koko is a gorilla with 4 piles of bananas: 36711. A guard gives her 8 hours to eat them all at whatever speed she chooses, then leaves. She can choose any integer eating speed k — bananas per hour — but she must eat from only one pile per hour, even if a pile has fewer bananas than her speed allows.
The most natural approach: start at k=1 and count up. Does k=1 finish in time? Does k=2? Keep going until you find a speed that works. This is a linear scan — O(max(piles) × n) operations in the worst case. For tiny inputs, it is fine. For real inputs, it collapses.
Below you can feel what that cost looks like at scale. Slide the maximum pile size up and watch the iteration count grow. You are looking for the speed at which the approach becomes untenable.
If `max(piles) =` 11
The key question is: do we need to check every candidate speed in order, or does the answer space have structure we can exploit? The next section shows you that structure firsthand — by building the scan manually on our small example until the pattern reveals itself.
You saw the linear scan explode to 4 billion iterations. Now try it yourself on a small input — 4 piles, 8 hours. Test each speed k=1 through k=4 in any order.
As the results accumulate, watch for a pattern in the feasibility column. Something predictable is hiding in the data — and once you see it, you will know exactly how to exploit it.
Each tap computes ceil(pile / k) for every pile and sums the results. Why ceiling? Koko must occupy a pile for the entire hour — even if she finishes early. A pile of 7 bananas at speed 4 takes 2 full hours: she eats 4 in hour one, then the remaining 3 in hour two. She cannot split that second hour with another pile. That ceiling is the heart of the feasibility check you are about to build by hand.
Pick a speed to test. Each tap runs the feasibility check — sum ceil(pile / k) across all 4 piles and see whether it fits inside h = 8 hours.