Koko Eating Bananas - Leetcode 875

Koko Eating Bananas - Leetcode 875

Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> 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 hhours.

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 <= 10<sup>4</sup>

  • piles.length <= h <= 10<sup>9</sup>

  • 1 <= piles[i] <= 10<sup>9</sup>

Solution in Golang

func minEatingSpeed(piles []int, h int) int {
  lo, hi, ans := 1, 1000000000, 1
  for lo <= hi {
    mid := (lo + hi) / 2
    if canEat(piles, h, mid){
      ans = mid 
      hi = mid -1 
    }else {
      lo = mid +1
    }
  }
  return ans 
}

func canEat(pile []int, timeLimit, speed int )bool {
  timeNeed := 0
  for _, banana := range pile {
    timeNeed = timeNeed + (banana + speed - 1) / speed
    if timeNeed > timeLimit {
      return false
    }
  }
  return true
}

This code is a Go implementation for finding the minimum eating speed required to eat all the bananas within a given time limit. The function minEatingSpeed takes in two parameters: piles, which is an array of integers representing the number of bananas in each pile, and h, which represents the time limit in hours.

The function initializes three variables: lo, hi, and ans. The lo and hi represents the lower and upper bounds for the eating speed, while ans stores the final answer. The function uses a binary search approach to find the minimum eating speed. It starts by setting lo to 1 and hi to a large number, here 1000000000.

The code then enters a while loop that runs until lo is less than or equal to hi. Inside the loop, it calculates the middle value mid using the formula (lo + hi) / 2. Then it calls the canEat function, passing in the piles, the time limit h, and the current eating speed mid.

If the canEat function returns true, it means it's possible to eat all the bananas within the given time limit using the current speed. In this case, the function updates the ans to the current mid value, indicating a possible minimum speed, and adjusts hi to mid - 1 to search for smaller values.

If the canEat function returns false, it means it's not possible to eat all the bananas within the time limit at the current speed. In this case, the function updates lo to mid + 1 to search for higher values.

The canEat function calculates the total time needed to eat all the bananas using the current speed. It iterates through each pile of bananas, calculates the time required for each pile at the given speed, and adds it to the total time. If the total time exceeds the given time limit, the function returns false. Otherwise, it returns true.

Finally, the minEatingSpeed function returns the final ans, which represents the minimum eating speed required to eat all the bananas within the given time limit.

Did you find this article valuable?

Support / ᴊʏᴏᴛɪʀᴍᴏʏ.ᴅᴇᴠ by becoming a sponsor. Any amount is appreciated!