Koko Eating Bananas
Program for Koko Eating Bananas Problem
You are given an array piles, where each element piles[i] represents the number of bananas in the i-th pile. You also have h hours to eat all the bananas. You can choose an eating rate of k bananas per hour. In each hour, you can eat up to k bananas from one pile.
If a pile has fewer than k bananas, you finish that pile but cannot switch to another pile during the same hour.
Your task is to find the minimum value of k that allows you to eat all the bananas within h hours.
Output: 2
Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2.
Output: 25
Constraints:
- 1 <= piles.length <= 1,000
- piles.length <= h <= 1,000,000
- 1 <= piles[i] <= 1,000,000,000
Program for Koko Eating Bananas Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(nlogm) time and O(1) space, where n is the size of the input array, and m is the maximum value in the array.
Hints for solving problems
Hint 1 :
Given h is always greater than or equal to the length of piles, can you determine the upper bound for the answer? How much time does it take Koko to eat a pile with x bananas?
Hint 2 :
It takes ceil(x / k) time to finish the x pile when Koko eats at a rate of k bananas per hour. Our task is to determine the minimum possible value of k. However, we must also ensure that at this rate, k, Koko can finish eating all the piles within the given h hours. Can you now think of the upper bound for k?
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Binary Search Method
1. Brute Force Method
Iterate through each possible eating speed from 1 to the maximum pile size and check if Koko can finish all the bananas within the given hours.
- Time complexity: O(m*n)
- Space complexity: O(1)
where n is the length of the input array piles and m is the maximum number of bananas in a pile.
Code
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int speed = 1;
while (true) {
long long totalTime = 0;
for (int pile : piles) {
totalTime += (pile + speed - 1) / speed;
}
if (totalTime <= h) {
return speed;
}
speed++;
}
}
};
public class Solution {
public int minEatingSpeed(int[] piles, int h) {
int speed = 1;
while (true) {
long totalTime = 0;
for (int pile : piles) {
totalTime += (int) Math.ceil((double) pile / speed);
}
if (totalTime <= h) {
return speed;
}
speed++;
}
}
}
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
speed = 1
while True:
totalTime = 0
for pile in piles:
totalTime += math.ceil(pile / speed)
if totalTime <= h:
return speed
speed += 1
return speed
class Solution {
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
minEatingSpeed(piles, h) {
let speed = 1;
while (true) {
let totalTime = 0;
for (let pile of piles) {
totalTime += Math.ceil(pile / speed);
}
if (totalTime <= h) {
return speed;
}
speed++;
}
}
}
2. Binary Search Method
Use binary search to find the minimum eating speed by searching between 1 and the maximum pile size, checking the feasibility of each mid-speed.
- Time complexity: O(n * log m)
- Space complexity: O(1)
where n is the length of the input array piles and m is the maximum number of bananas in a pile.
Code
class Solution {
public:
int minEatingSpeed(vector& piles, int h) {
int l = 1;
int r = *max_element(piles.begin(), piles.end());
int res = r;
while (l <= r) {
int k = (l + r) / 2;
long long totalTime = 0;
for (int p : piles) {
totalTime += ceil(static_cast(p) / k);
}
if (totalTime <= h) {
res = k;
r = k - 1;
} else {
l = k + 1;
}
}
return res;
}
};
public class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1;
int r = Arrays.stream(piles).max().getAsInt();
int res = r;
while (l <= r) {
int k = (l + r) / 2;
long totalTime = 0;
for (int p : piles) {
totalTime += Math.ceil((double) p / k);
}
if (totalTime <= h) {
res = k;
r = k - 1;
} else {
l = k + 1;
}
}
return res;
}
}
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
totalTime = 0
for p in piles:
totalTime += math.ceil(float(p) / k)
if totalTime <= h:
res = k
r = k - 1
else:
l = k + 1
return res
class Solution {
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
minEatingSpeed(piles, h) {
let l = 1;
let r = Math.max(...piles);
let res = r;
while (l <= r) {
const k = Math.floor((l + r) / 2);
let totalTime = 0;
for (const p of piles) {
totalTime += Math.ceil(p / k);
}
if (totalTime <= h) {
res = k;
r = k - 1;
} else {
l = k + 1;
}
}
return res;
}
}
