Start learning free

LESSON 334 OF 539 · BINARY SEARCH

Koko Eating Bananas in C#: 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 an array 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

    The method MinEatingSpeed receives an int[] of banana piles and an int h, the number of hours available. Koko picks a speed k in bananas per hour. Each hour she works on one pile and eats up to k bananas from it. If the pile has fewer than k, she finishes it and wastes the rest of that hour. A pile of p bananas therefore takes p / k hours, rounded up. The method 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, while at speed 3 they take 1 + 2 + 3 + 4 = 10. For {30, 11, 23, 4, 20} with h = 5 there are as many hours as piles, so every pile must take one hour and the answer is the biggest pile, 30. With h = 6 the answer is 23.

    Approach: binary search on the answer, not on the data

    Nothing in the input is sorted, so what is there to binary search? The speeds. If Koko finishes in time at speed k, she also finishes at any faster speed, and if she doesn't, no slower speed works either. So going through the speeds 1, 2, 3, and so on, the answer is "too slow" up to some point and "fast enough" from then on, with a single switch. Binary search finds that switch.

    The search range is easy to bound. The slowest sensible speed is 1. The fastest we ever need is the biggest pile: at that speed every pile takes one hour, and since there are never more piles than hours, it always works. So the answer lies between 1 and piles.Max().

    Trying every speed from 1 up costs O(n · m), where m is the biggest pile. Binary search needs only about log2(m) speeds (about 30 for a billion bananas), and each test of a speed reads the piles once, so the total is O(n log m).

    On {3, 6, 7, 11} with h = 8, the search tries speed 6 (6 hours, fast enough, so look lower), then 3 (10 hours, too slow, so look higher), then 4 (8 hours, fast enough). The range is then empty and the answer is 4.

    Step by step

    1. Set the range. left = 1 and right = piles.Max(). Max() comes from System.Linq and returns the largest element.
    2. Remember a speed that works. answer starts at right, which is known to be fast enough, so there is a valid result even before the first test.
    3. Loop while left <= right. When they are equal, one speed is still untried.
    4. Take the middle speed: k = left + (right - left) / 2.
    5. Ask the helper. Hours(piles, k), written later, returns the hours needed at speed k. If that is at most h, the speed works.
    6. If it works, store k in answer first, then look for something slower with right = k - 1. Store before moving: the search never returns to k, and it may be the best speed there is.
    7. Otherwise it is too slow, and so is every slower speed, so left = k + 1.
    8. Return answer. When the loop ends, every speed below answer was ruled out.
    9. Write Hours. It returns a long, starts total at 0 and adds, for each pile, the pile's hours rounded up. Integer-only rounding up is (pile + k - 1) / k: a pile of 7 at speed 3 takes (7 + 2) / 3 = 3 hours, while 7 / 3 alone gives 2 and forgets the last hour. An exact multiple doesn't move: (6 + 2) / 3 is still 2.

    The solution in C#

    class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int left = 1, right = piles.Max();
        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;
    }

    public long Hours(int[] piles, int k) {
        long total = 0;
        foreach (int pile in piles) {
            total += (pile + k - 1) / k;
        }
        return total;
    }
}

    The C# details worth knowing:

    • Why Hours returns a long. With 10,000 piles of 1,000,000,000 bananas, speed 1 takes 10,000,000,000,000 hours. An int tops out at 2,147,483,647 and wraps silently: adding those same ten thousand values in an int variable gives 1316134912, a wrong but plausible-looking number. Because total is a long, the comparison Hours(piles, k) <= h is also done in 64 bits.
    • total += (pile + k - 1) / k computes the division in int, then widens the result into the long. That is safe here: pile + k - 1 is at most 1,999,999,999 when both are 1,000,000,000, which still fits in an int.
    • Integer division truncates. That is why adding k - 1 before dividing rounds up. Math.Ceiling would need floating point, which is slower and less precise for big values.
    • The midpoint form. left + (right - left) / 2 never overflows, unlike (left + right) / 2 for large ranges.
    • foreach (int pile in piles) reads each element in turn. The loop variable can't be assigned to, which is fine because the method only reads it.

    Complexity

    Let n be the number of piles and m the biggest pile.

    Time: O(n log m). The search range has m speeds and each pass halves it, so about log2(m) passes. Each pass calls Hours, which makes one pass over the n piles.

    Space: O(1). A few variables, with no extra collections.

    Edge cases and common mistakes

    • One pile. {1000000000} with h = 1 returns 1000000000, and with h = 312884469 for a pile of 312884470 it returns 2, since speed 1 would need 312884470 hours.
    • As many hours as piles. The answer is the biggest pile, which is exactly the upper end of the range.
    • Rounding down. Using pile / k gives answers that are too small, because the last partial hour is lost.
    • An int total. It overflows at slow speeds and may even turn negative, which would make a slow speed look fast enough.
    • Forgetting answer = k. Without it, the code has no way to know which speed was the last one that worked.
    • Starting left at 0. A speed of 0 would divide by zero in Hours, which throws DivideByZeroException.

    Testing

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