Start learning free

LESSON 330 OF 535 · BINARY SEARCH

Koko Eating Bananas in C++: O(n log m) Binary Search on the Answer

Practice O(n log m) Read the full explanation

Koko loves to eat bananas. There are n piles of bananas, and pile i has piles[i] bananas. The guards have gone and will come back in h hours.

Koko chooses an eating speed of k bananas per hour. Each hour, she picks one pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and eats nothing more during that hour. So a pile of p bananas takes her p / k hours, rounded up.

Given a vector of integers piles and an integer h, return the smallest integer speed k that lets Koko eat all the bananas within h hours.

 

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours, just in time. At speed 3 they would take 1 + 2 + 3 + 4 = 10 hours, too many.

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: There are as many hours as piles, so every pile must be eaten in one hour, and the biggest pile has 30 bananas.

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: At speed 23 the piles take 2 + 1 + 1 + 1 + 1 = 6 hours. At speed 22 the pile of 23 takes 2 hours too, so they take 2 + 1 + 2 + 1 + 1 = 7 hours.

 

Constraints:

  • 1 <= n <= 104, where n is the number of piles
  • n <= h <= 109
  • 1 <= piles[i] <= 109

Note:

Your algorithm should run in O(n log m) time, where m is the biggest pile, and use O(1) extra space.

At a slow speed the hours add up fast: 104 piles of 109 bananas take 1013 hours at speed 1, far more than a 32-bit integer can hold.

STEP 1 OF 13
    Ctrl + Enter to check

    C++ · BINARY SEARCH

    Koko Eating Bananas in C++, explained

    Problem overview

    Koko has n piles of bananas, piles[i] in pile i, and h hours before the guards return. She picks a speed of k bananas per hour. Each hour she works on a single pile and eats up to k bananas from it; if the pile has fewer, she finishes it and wastes the rest of the hour. A pile of p bananas therefore takes p / k hours, rounded up.

    minEatingSpeed receives the vector<int> piles and the int h, and returns the smallest whole speed that finishes every pile within h hours.

    For piles = {3, 6, 7, 11} and h = 8 the answer is 4. At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours. At speed 3 they take 1 + 2 + 3 + 4 = 10 hours, which is too many. For piles = {30, 11, 23, 4, 20}, h = 5 gives 30, because five hours for five piles means one pile per hour, and h = 6 gives 23.

    The statement asks for O(n log m) time, where m is the biggest pile, and O(1) extra space.

    Approach: binary search on the speed

    Trying speeds 1, 2, 3 and so on until one fits could take as many as m attempts, each costing O(n) to count the hours. The faster idea is to search over the speeds themselves.

    The speeds have a useful property. If Koko finishes in time at speed k, she also finishes at any faster speed. If she doesn't finish at k, no slower speed helps. So the speeds turn from "too slow" to "fast enough" exactly once, and binary search can find the turning point. This is binary search on the answer: instead of looking for a value in an array, the search asks a yes-or-no question about a candidate speed.

    The range of candidates runs from 1 up to the biggest pile. At the speed of the biggest pile every pile takes exactly one hour, and the statement guarantees h >= n, so that speed always works. No answer is ever bigger.

    Here is the search on piles = {3, 6, 7, 11} with h = 8, printing each candidate and the hours it needs:

    left=1 right=11 k=6 hours=6
left=1 right=5 k=3 hours=10
left=4 right=5 k=4 hours=8

    Speed 6 needs 6 hours, which fits, so it is recorded and the search looks lower. Speed 3 needs 10, which doesn't fit, so the search moves above 3. Speed 4 needs 8, which fits, and recording it leaves the range 4..3, which is empty. The answer is 4.

    Step by step

    1. Set the range. left is 1, the slowest speed, and right is the biggest pile, found with *max_element(piles.begin(), piles.end()). The function returns an iterator, and the * reads the value it points to.
    2. Keep an answer that starts at right. That speed is known to work, so the variable holds a valid answer even before the search starts.
    3. Loop while left <= right. When the two are equal, one speed is still untried.
    4. Pick the middle speed k as left + (right - left) / 2. It rounds down, and it can't overflow the way left + right could.
    5. Ask the question: does hours(piles, k) come to at most h? The helper is written afterwards.
    6. If yes, k works. Store it in answer first, because the search never returns to it and it may be the smallest, then look for something slower with right = k - 1.
    7. If no, k and every slower speed are too slow, so set left = k + 1.
    8. Return answer. When the loop ends, every speed below it was too slow.
    9. Write the helper hours. It takes piles by reference, like the main method, and the speed k, and returns a long long.
    10. Keep a long long total that starts at 0 and add each pile's hours to it.
    11. Round up with integers only. For each pile add (pile + k - 1) / k. A pile of 7 at speed 3 gives (7 + 2) / 3, which is 3, while 7 / 3 alone is 2 and forgets the last hour. An exact multiple doesn't move: (6 + 2) / 3 is 2.
    12. Return total, the hours Koko needs at speed k.

    The solution in C++

    class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = *max_element(piles.begin(), piles.end());
        int answer = right;
        while (left <= right) {
            int k = left + (right - left) / 2;
            if (hours(piles, k) <= h) {
                answer = k;
                right = k - 1;
            } else {
                left = k + 1;
            }
        }
        return answer;
    }

    long long hours(vector<int>& piles, int k) {
        long long total = 0;
        for (int pile : piles) {
            total += (pile + k - 1) / k;
        }
        return total;
    }
};

    The C++ details worth a closer look:

    • Why long long for the hours. At speed 1, 10,000 piles of 1,000,000,000 bananas take 10,000,000,000,000 hours, far above the largest int (2,147,483,647). The helper returns exactly that number, and a long long holds up to about 9.2 quintillion. With an int total, signed overflow is undefined behaviour in C++, so the slow speeds could produce wrong answers.
    • The comparison hours(piles, k) <= h compares a long long with an int. The int is converted to long long, so nothing is lost.
    • The rounding sum stays in int. pile + k - 1 is at most 1,000,000,000 + 1,000,000,000 - 1, which is below 2,147,483,647 because k never exceeds the biggest pile. Only the running total needs the wider type.
    • Calling a member function defined later. Inside a class, member functions can call each other whatever the order, so minEatingSpeed can use hours even though it is written below.
    • max_element needs a non-empty range, which the constraints give (n >= 1). On an empty vector, dereferencing its result would be undefined behaviour.

    Complexity

    Time: O(n log m). The range holds m speeds and halves with each pass, so the loop runs about log2(m) times, around 30 for a biggest pile of a billion. Each pass calls hours, which visits all n piles. Finding the maximum adds one O(n) pass.

    Space: O(1). Only a few integers are kept. piles is passed by reference, so it isn't copied.

    Edge cases and common mistakes

    • One pile. {5} with h = 3 returns 2: speed 2 takes 3 hours, and speed 1 takes 5. {1000000000} with h = 2 returns 500,000,000.
    • As many hours as piles. {1, 1, 1} with h = 3 returns 1, and h = n in general forces the speed of the biggest pile.
    • Huge input. With 10,000 piles of 1,000,000,000 and h = 10000, the answer is 1,000,000,000. With h = 20000 it is 500,000,000, and with h = 1000000000 it is 10,000. The search works with these because the hours are a long long.
    • Rounding down. Writing pile / k loses the last partial hour of every pile. The result is a speed that is too slow.
    • Floating point. ceil((double)pile / k) also works for these sizes, but the integer form (pile + k - 1) / k is simpler and exact.
    • Forgetting to store k. Moving right to k - 1 without saving k loses the best speed found so far.
    • Starting left at 0. The speed 0 divides by zero in hours.

    Testing

    • piles = {3, 6, 7, 11}, h = 8 gives 4.
    • piles = {30, 11, 23, 4, 20}, h = 5 gives 30, and h = 6 gives 23.
    • piles = {5}, h = 3 gives 2.
    • piles = {1, 1, 1}, h = 3 gives 1.
    • piles = {1000000000}, h = 2 gives 500000000.
    • piles = {312884470}, h = 312884469 gives 2.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free