875-koko-eating-bananas

Try it on leetcode

Description

Koko loves to eat bananas. There are n piles of bananas, the ith 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 will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

 

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

 

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Solution(Python)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        return self.binarySearch(piles, h)

    # minimum possible speed will be 1
    # maximum possible speed will be m largest pile size
    # which gives us range
    # then try every possible speed values starting from lowest speed
    # until condition is met
    #
    # Time Complexity: O(mn)
    # Space Complexity: O(1)
    def bruteforce(self, piles: List[int], h: int) -> int:
        speed = 1

        while True:
            hour_spend = 0
            for pile in piles:
                hour_spent += ceil(pile / speed)
            if hour_spent <= h:
                return speed
            else:
                speed += 1

    # since bruteforce searches on the range of increasing list
    # binary search will halves the  search space by log m
    #
    # binary search control relies on finding the condition of spearater
    # line between the search space
    # if x banana per second satisfies means x+1 banana per second also
    # satisfies the time criteria so ignore x+1
    # if x bps doesnot satifies then ignore x-1
    # Time Complexity: O(nlogM)
    # Space Complexity:O(1)
    def binarySearch(self, piles: List[int], h: int) -> int:
        left = 1
        right = max(piles)

        while left < right:
            mid = (left + right) // 2
            hour_spend = 0
            for pile in piles:
                hour_spend += ceil(pile / mid)

            if hour_spend <= h:
                right = mid
            else:
                left = mid + 1
        return left