Leetcode 875 || Koko Eating Bananas

Problem Link

https://leetcode.com/problems/koko-eating-bananas/description/

Discussion and Solution

Inputs

piles : An array contains how many bananas ith pile has

h : Within h hours Koko has to eat all the bananas

Output

k : Minimum speed of eating bananas.

Other conditions

• Koko can not eat more than k bananas in an hour

• If one pile has bananas less than k, Koko will eat all the bananas from that pile. And Koko won't eat bananas from another pile in that hour.

Look at the example below to understand better :

piles = [3,6,7,11]
k = 1 --- total time = ceil(3/1) + ceil(6/1) + ceil(7/1) + ceil(11/1) = 3+6+7+11 = 27 hours
k = 2 --- total time = ceil(3/2) + ceil(6/2) + ceil(7/2) + ceil(11/2) = 2+3+4+6 = 15 hours
k = 3 --- total time = ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1+2+3+4 = 10 hours

# here, we are taking the ceil, cause, 
# for the last pile when k = 3
# Koko can eat 9 bananas in 3 hours and then 2 bananas remain at that pile. So in 4th hour Koko eats only those 2 bananas from that pile.

So the minimum speed Koko can eat is 1.

If eating speed, k = max(piles) , then Koko can finish eating all the bananas in len(piles) hours. As Koko eats from a single pile in a single hour, max(piles) is the maximum speed Koko needs to eat at.

So as we get the range of eating we can think of using all possible values in this range to find out the minimum speed Koko needs to eat at to finish all the bananas.

But if the range is bigger, time complexity will increase eventually.

So Let's implement Binary Seach here to find out the minimum speed.

Code

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        minn = 1
        maxx = max(piles) # maximum speed koko needs to eat at

        while minn<maxx:
            mid = minn+(maxx-minn)//2
            # count hr for each k(mid) speed 
            hr = 0
            for i in piles:
                hr += math.ceil(i/mid)
                # if hr cross h no need to check futher 
                if hr>h:
                    break
            # hr>h means Koko needs more time than h. So Koko has to increase eating speed 
            if hr>h:
                minn = mid+1
            # if hr<=h, search if any other minimum k possible as koko loves to eat solowly 
            else:
                maxx = mid

        return maxx

Here you can return minn instead of maxx as the loops break when minn==maxx

Thanks for reading. Happy coding.