Koko Eating Bananas

Posted on | Post modified: | In , |
Words count: 597 words | Reading time ≈ 3 minutes

Problem Description

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour. Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Koko eating Banana

Example

1
2
Input: piles = [3,6,7,11], H = 8
Output: 4
1
2
Input: piles = [30,11,23,4,20], H = 5
Output: 30
1
2
Input: piles = [30,11,23,4,20], H = 6
Output: 23

Ideas

The way to tackle this question is to find out a way to get the minimum possible K. The value for K is clearly limited from 1 to the greatest number in the piles array (if setting K to maximum number in the array then any number greater than K will only result in longer time to finish)

Of course we could iterate from 1 to the greatest number to find out K, then why don’t we use binary search? The way it works is that if we found some K that doesn’t allow Koko to have all the bananas in limited time H, then any number smaller than K will not work either. Same thing goes to the case that we found some K that does allow Koko to enjoy all bananas within time H, we can then safely try smaller numbers as they might also fulfill the term.

Now that we have a nice way to find K, the only thing left here is to check if K is good (Koko get to eat all bananas within H hours) or not (Koko get caught by the guard). We can simply go through the array to calculate the time needed according the the description.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int low = 1;
        int high = Integer.MIN_VALUE;
        for (int p : piles) {
            high = Math.max(high, p);
        }
        
        while (low < high) {
            int K = low + (high - low) / 2;
            if (finish(piles, K, H)) {
                high = K;
            } else {
                low = K + 1;
            }
        }
        
        return low;
    }
    
    private boolean finish(int[] piles, int K, int H) {
        int hours = 0;
        for (int p : piles) {
            if (p <= K) {
                hours++;
            } else {
                hours += p / K + 1;
            }
        }
        return hours <= H;
    }
}

Complexity and Optimizaiton

Suppose n is the length of the piles array, the method finish takes O(n) as it iterates over the array once. In minEatingSpeed finish is called inside the binary search loop. Therefore, the time complexity is O(nlog(K)) and space complexity is O(1).

There are still something we could improve in the finish method. Assuming n is smaller than K, then we could first sort the piles array in minEatingSpeed, then use binary seach as well in finish to find out the minimum p larger than K, in this way there is no need to iterate the elements before p.

Optimal Solution

The best solution is to let Koko finish all bananas in the way she wants, simply because she is a smart gorilla. (Will you ask a bee how to solve the travelling salesman problem?)

-------------EOFThanks for reading:)-------------
0%