SyntaxPilot
Courses/DSA and Coding Problems/Lesson 14
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 14 of 90

Binary search on the answer: Koko eating bananas, aggressive cows

queued

These are the notes for DSA episode 14, the third episode of the binary search block. In episodes 12 and 13 binary search needed a sorted array. Here there is no sorted array at all: we binary search over the range of possible answers. Two classic problems fall to it: Koko Eating Bananas (LeetCode 875) and Aggressive Cows (SPOJ AGGRCOW, also on GeeksforGeeks). Trying every answer one by one takes up to 10⁹ tries and times out; binary search on the answer needs about 30. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Your exam is tomorrow. Four chapters are left, with 3, 6, 7 and 11 pages, and you have 8 hours. You study in one-hour slots and each slot is for one chapter only: if a chapter finishes in the middle of a slot, you rest for the rest of that hour. Reading fast tires you and you remember less, so: what is the slowest speed, in pages per hour, that still finishes everything in 8 hours? (Answer: 4.)

Problem statement (Koko Eating Bananas, LeetCode 875)

There are n piles of bananas, piles[i] in pile i, and h hours. Koko picks a speed k: each hour she eats up to k bananas from one pile (if the pile has fewer, she eats them all and waits for the next hour). A pile of x bananas takes ⌈x / k⌉ hours (rounded up). Return the smallest k that finishes all piles within h hours.

Constraints: 1 <= n <= 10⁴, n <= h <= 10⁹, 1 <= piles[i] <= 10⁹.

piles h answer why
[3, 6, 7, 11] 8 4 1 + 2 + 2 + 3 = 8 hours
[30, 11, 23, 4, 20] 5 30 5 piles in 5 hours: every pile in one hour
[30, 11, 23, 4, 20] 6 23 the pile of 30 now takes 2 hours
[1000000000] 2 500000000
[5] 10 1 plenty of time: the slowest speed

Solution 1: brute force (try speed 1, 2, 3, ...)

import java.util.*;

public class Main {
    static long hours(int[] p, int k) {
        long h = 0;
        for (int x : p) h += (x + k - 1) / k;
        return h;
    }
    static int minSpeed(int[] p, int h) {
        int k = 1;
        while (hours(p, k) > h) k++;
        return k;
    }
    public static void main(String[] args) {
        System.out.println(minSpeed(new int[]{3, 6, 7, 11}, 8));
        System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 5));
    }
}

Output:

4
30

(x + k - 1) / k is integer division rounded up (the ceiling). The total is a long, because at small speeds it can reach n × 10⁹.

Now a real input: one lakh piles of 10⁹ bananas each, and 2 lakh hours (the answer is 5 × 10⁸):

        int[] p = new int[100000];
        Arrays.fill(p, 1000000000);
        long t0 = System.nanoTime();
        int k = minSpeed(p, 200000);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(k + "   " + ms + " ms");

Result: Time Limit Exceeded.

Why it is slow

  • Trying one speed costs O(n): one pass over the piles.
  • There can be up to max(pile) = 10⁹ speeds to try, so the brute force is O(n · max). Here: 5 × 10⁸ tries × 10⁵ piles.
  • We check the answers one by one, in order, like reading a dictionary from page 1.

The key insight: a yes/no question that is sorted

Forget the piles and look at the answers. For every speed k from 1 to the biggest pile, write the hours needed, and ask "does it finish within h?":

speed k 1 2 3 4 5 6 7 8 9 10 11
hours 27 15 10 8 8 6 5 5 5 5 4
<= 8 ? no no no yes yes yes yes yes yes yes yes

A faster speed never needs more hours, so the yes/no row is all no's, then all yes's. It is sorted! A condition like this is called monotonic. We want the first yes, which is a lower bound, exactly the template from episode 12, applied to the range of answers instead of an array.

Binary search on the answer:

  • Search space: speeds lo = 1 ... hi = max(pile) (speed max(pile) always works: one hour per pile).
  • Question: ok(k) = hours(k) <= h.
  • ok(mid) → mid might be the answer, keep it: hi = mid. Otherwise mid is too slow: lo = mid + 1.
  • log₂(10⁹) ≈ 30 checks, each O(n).

Dry run: minSpeed([3, 6, 7, 11], 8)

Step lo hi mid hours(mid) ok? Action
1 1 11 6 6 yes hi = 6
2 1 6 3 10 no lo = 4
3 4 6 5 8 yes hi = 5
4 4 5 4 8 yes hi = 4
5 4 4 answer 4

Solution 2: Koko, typed live

import java.util.*;

public class Main {
    static long hours(int[] p, int k) {
        long h = 0;
        for (int x : p) h += (x + k - 1) / k;
        return h;
    }
    static int minSpeed(int[] p, int h) {
        int lo = 1, hi = 1;
        for (int x : p) hi = Math.max(hi, x);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hours(p, mid) <= h) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    public static void main(String[] args) {
        System.out.println(minSpeed(new int[]{3, 6, 7, 11}, 8));
        System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 5));
        System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 6));
        System.out.println(minSpeed(new int[]{1000000000}, 2));
        System.out.println(minSpeed(new int[]{5}, 10));
    }
}

Output:

4
30
23
500000000
1

The input that timed out (10⁵ piles of 10⁹, h = 2 × 10⁵) printed:

500000000   23 ms

About 30 checks of one lakh piles each. (x + k - 1 stays inside int here because x, k <= 10⁹, so it is at most about 2 × 10⁹ - 1 < 2,147,483,647.)

The second problem: exam hall seats (Aggressive Cows)

An exam hall corridor has seats at fixed positions: 1, 2, 4, 8 and 9 metres. Three students write the exam, and the invigilator wants to stop copying: seat them so that the closest two are as far apart as possible. In the classic version these are stalls in a barn and cows that fight: Aggressive Cows. We maximise the minimum gap.

Flip it into a yes/no question: canSeat(d) = can every pair be at least d apart?

  • Greedy check, O(n): sort the seats, put the first student at the first seat, then walk right and seat the next student at the first seat that is at least d from the last one. Taking the earliest possible seat never hurts: it leaves the most room for everyone after.
  • Answers for every d: 1 yes, 2 yes, 3 yes, 4 no, 5 no ... This time it is yes, then no (a bigger gap only gets harder). We want the last yes = first no - 1, the same trick as "last occurrence = lowerBound(t + 1) - 1" in episode 12.

Greedy check for d = 3: seat at 1; next seat >= 4 is 4; next seat >= 7 is 8 → 3 seated, yes. For d = 4: 1, then >= 5 is 8, then >= 12 none → only 2, no. Answer 3.

import java.util.*;

public class Main {
    static boolean canSeat(int[] s, int c, int d) {
        int placed = 1, last = s[0];
        for (int i = 1; i < s.length; i++)
            if (s[i] - last >= d) { placed++; last = s[i]; }
        return placed >= c;
    }
    static int maxGap(int[] s, int c) {
        Arrays.sort(s);
        int lo = 1, hi = s[s.length - 1] - s[0] + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (!canSeat(s, c, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo - 1;
    }
    public static void main(String[] args) {
        System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 3));
        System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 2));
        System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 5));
        System.out.println(maxGap(new int[]{0, 1000000000}, 2));
    }
}

Output:

3
8
1
1000000000

hi is one more than the largest possible gap, so the first "no" is always inside [lo, hi]. Two students sit at the two ends (8); five students use every seat (1).

The same solutions in C++ and Python

#include <bits/stdc++.h>
using namespace std;

long long hoursAt(const vector<int>& p, int k) {
    long long h = 0;
    for (int x : p) h += (x + (long long)k - 1) / k;   // ceil(x / k)
    return h;
}
int minSpeed(const vector<int>& p, long long h) {
    int lo = 1, hi = *max_element(p.begin(), p.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursAt(p, mid) <= h) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
bool canSeat(const vector<int>& s, int c, int d) {
    int placed = 1, last = s[0];
    for (size_t i = 1; i < s.size(); i++)
        if (s[i] - last >= d) { placed++; last = s[i]; }
    return placed >= c;
}
int maxGap(vector<int> s, int c) {
    sort(s.begin(), s.end());
    int lo = 1, hi = s.back() - s[0] + 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (!canSeat(s, c, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo - 1;
}
int main() {
    cout << minSpeed({3, 6, 7, 11}, 8) << " " << minSpeed({30, 11, 23, 4, 20}, 5) << " "
         << minSpeed({30, 11, 23, 4, 20}, 6) << " " << minSpeed({1000000000}, 2) << " " << minSpeed({5}, 10) << "\n";
    cout << maxGap({1, 2, 8, 4, 9}, 3) << " " << maxGap({1, 2, 8, 4, 9}, 2) << " "
         << maxGap({1, 2, 8, 4, 9}, 5) << " " << maxGap({0, 1000000000}, 2) << "\n";
}
def hours(p, k):
    return sum((x + k - 1) // k for x in p)      # ceil(x / k)

def min_speed(p, h):
    lo, hi = 1, max(p)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(p, mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_seat(s, c, d):
    placed, last = 1, s[0]
    for x in s[1:]:
        if x - last >= d:
            placed += 1
            last = x
    return placed >= c

def max_gap(s, c):
    s = sorted(s)
    lo, hi = 1, s[-1] - s[0] + 1
    while lo < hi:
        mid = (lo + hi) // 2
        if not can_seat(s, c, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo - 1

print(min_speed([3, 6, 7, 11], 8), min_speed([30, 11, 23, 4, 20], 5),
      min_speed([30, 11, 23, 4, 20], 6), min_speed([10**9], 2), min_speed([5], 10))
print(max_gap([1, 2, 8, 4, 9], 3), max_gap([1, 2, 8, 4, 9], 2),
      max_gap([1, 2, 8, 4, 9], 5), max_gap([0, 10**9], 2))

Both print:

4 30 23 500000000 1
3 8 1 1000000000

Two real bugs

Bug 1: lo = 0 → / by zero

        int lo = 0, hi = 1;

minSpeed(new int[]{5}, 10) crashed:

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at Main.hours(Main.java:4)

The answer is 1, so the search walks down to lo = 0, hi = 1, mid = 0, and hours divides by a speed of 0. We are searching answers, not indexes: start lo at the smallest answer that makes sense (speed 1).

Bug 2: forgetting to sort

Without Arrays.sort(s), maxGap(new int[]{1, 2, 8, 4, 9}, 3) printed 1 (should be 3). No error, just a wrong answer. The greedy walk assumes seats come left to right, and hi uses the first and last elements as the corridor's two ends; both are only true after sorting.

The recipe: binary search on the answer

  1. The answer is a number inside a range [lo, hi] you can name.
  2. Write ok(x): is x good enough? Usually a greedy pass, O(n).
  3. Check it is monotonic: no ... no yes ... yes (find the first yes) or yes ... yes no ... no (find the last yes = first no - 1).
  4. Use the lower-bound template to find where it flips.

Hints in the statement: "minimise the maximum", "maximise the minimum", "the smallest value such that ...". The same recipe solves Capacity to Ship Packages Within D Days (1011), Split Array Largest Sum (410), Book Allocation, Minimum Days to Make m Bouquets (1482), Painter's Partition.

Complexity

Approach Time Extra space 10⁵ piles of 10⁹
Koko, try k = 1, 2, 3, ... O(n · max) O(1) Time Limit Exceeded
Koko, binary search on k O(n · log max) O(1) 23 ms
Cows, try every d O(n log n + n · range) O(1) besides the sort
Cows, binary search on d O(n log n + n · log range) O(1) besides the sort

Common mistakes

Mistake What you see Why Fix
int lo = 0 for a speed ArithmeticException: / by zero mid can become 0 lo = smallest valid answer (1)
maxGap without Arrays.sort maxGap({1, 2, 8, 4, 9}, 3) = 1 greedy needs seats left to right sort first
x / k for the hours minSpeed({3, 6, 7, 11}, 8) = 3 (should be 4) integer division rounds down (x + k - 1) / k rounds up
int total hours can overflow: 10⁴ piles × 10⁹ hours at k = 1 = 10¹³ sum bigger than 2,147,483,647 long
hi = mid - 1 when ok(mid) can skip the answer mid itself may be the first yes hi = mid
Cows: returning lo instead of lo - 1 one too big lo ends on the first no lo - 1

Mini project: the study planner

Read the page counts of your chapters and the hours left. Print the slowest safe speed (minSpeed) and a timetable: for each chapter, how many one-hour slots it takes at that speed. Extension: given a maximum speed you can actually manage, print the minimum hours you need instead (binary search on hours, with the same ok idea).

Practice

  1. Capacity to Ship Packages Within D Days (LeetCode 1011): weights in order, the smallest ship capacity that ships everything in days days.
Solution

Answer range: lo = max(weight) (a package can't be split), hi = sum(weights). ok(cap) = greedily fill each day up to cap and count days; ok is monotonic (bigger capacity, fewer days). First yes:

    static int shipWithinDays(int[] w, int days) {
        int lo = 0, hi = 0;
        for (int x : w) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int need = 1, cur = 0;
            for (int x : w) {
                if (cur + x > mid) { need++; cur = 0; }
                cur += x;
            }
            if (need <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

shipWithinDays({1, 2, ..., 10}, 5) printed 15.

  1. Split Array Largest Sum (LeetCode 410): split into k non-empty contiguous parts, minimise the largest part's sum.
Solution

It is the same function as practice 1, with days = k: shipWithinDays({7, 2, 5, 10, 8}, 2) printed 18 ([7, 2, 5] | [10, 8]).

  1. Book allocation: n books with page counts in order, m students, each gets a contiguous block; minimise the maximum pages any student reads.
Solution

Same recipe again. For pages {12, 34, 67, 90} and 2 students the program printed 113 (12 + 34 + 67 | 90).

  1. Why is "take the earliest seat" safe in the cows check?
Solution

Exchange argument: take any valid seating. Move its first student to the first seat; gaps only grow. Then move each next student to the earliest seat at least d from the previous one; this seat is at or before theirs, so the remaining students have at least as much room. So if any seating works, the greedy one does too.

Quick quiz

What does minSpeed(new int[]{10, 10}, 4) return?

  • 5
  • 10
  • 4
  • 3
Answer

5. At k = 5 each pile takes 2 hours, 4 in total: fits. At k = 4 each pile takes 3 hours, 6 in total: too many. The first yes is 5.

Interview questions

  1. When can you binary search on the answer? When the answer is a number in a known range and a yes/no check on a candidate is monotonic.
  2. How do you choose lo and hi? The smallest and largest answers that make sense: speed 1 to max(pile); capacity max(weight) to sum(weights).
  3. First yes or last yes? "Smallest that works" is the first yes (ok(mid) → hi = mid). "Largest that works" is the last yes: find the first no and subtract 1.
  4. What is the complexity? O(cost of ok × log(range)): O(n log max) for Koko.
  5. Why long for the hours? At small speeds the total can reach n × 10⁹, far beyond int.
  6. Why does the cows problem need sorting? The greedy check walks seats left to right and uses the first and last as the corridor's ends.

Glossary

Term Meaning
Search space The set of values being searched; here the range of possible answers, not array indexes
Binary search on the answer Binary searching that range with a yes/no check on each candidate
Predicate ok(x) A function that answers yes or no for a candidate answer x
Monotonic Changes from no to yes (or yes to no) only once as x grows
Lower bound The first position where the condition becomes true (episode 12)
Ceiling division ⌈x / k⌉, division rounded up; in integers (x + k - 1) / k
Greedy Making the best local choice at each step (earliest seat) without going back
Minimise the maximum / maximise the minimum Typical wording of binary-search-on-the-answer problems
ArithmeticException: / by zero Java's runtime error for integer division by zero
Integer overflow A result bigger than the type's maximum (2,147,483,647 for int), which wraps to a wrong value
Time Limit Exceeded (TLE) The program is too slow for the judge's limit (8 s in the SyntaxPilot compiler)
long Java's 64-bit integer, up to about 9.2 × 10¹⁸

Summary

  • When the answer is a number in a range and "is x good enough?" is monotonic, binary search the answer.
  • Koko: first speed k in [1, max] with hours(k) <= h, hours rounded up, totals in long.
  • Exam seats / aggressive cows: sort, greedy canSeat(d), answer = first d that fails, minus 1.
  • Start the range at the smallest valid answer (lo = 0 divided by zero).
  • O(n log range) instead of O(n × range): 30 checks instead of 5 × 10⁸.

Next episode: Median of Two Sorted Arrays (hard).