Problem Statement
Koko loves to eat bananas, and there is a pile of bananas in each of the n piles. Koko has n hours to eat all the bananas. The task is to find the minimum integer eating speed k (in bananas per hour) such that Koko can eat all the bananas within n hours.
Examples
Example 1:
Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation:
Remember Koko can never move to the next pile until she finish the
current pile. If any pile has 3 banana and we are saying 2 banana per hour
then Koko will take 2 hours to eat these 3 bananas, ideally it should take
1.5 hours. We just cant carry the time to next pile
If we are saying 2 bananas per hour:
For the first hour she will eat 2 bananas
And in the next hour she will eat remaining 1 bananas.
So, we have to consider the ceil value of bananas.
If Koko eats at speed of 1 bananas per hour, she will takes:
Pile 1: ceil(3/1) = 3
Pile 2: ceil(6/1) = 6
Pile 3: ceil(7/1) = 7
Pile 4: ceil(11/1) = 11
Total = 3 + 6 + 7 + 11 = 27
If Koko eats at spped of 2 bananas per hour, she will takes:
Pile 1: ceil(3/2) = 2
Pile 2: ceil(6/2) = 3
Pile 3: ceil(7/2) = 4
PIle 4: ceil(11/2) = 6
Total = 2 + 3 + 4 + 6 = 15
If Koko eats at speed of 3 bananas per hour, she will takes:
Pile 1: ceil(3/3) = 1
Pile 2: ceil(6/3) = 2
Pile 3: ceil(7/3) = 3
Pile 4: ceil(11/3) = 4
Total = 1 + 2 + 3 + 4 = 10
If Koko eats at a speed of 4 bananas per hour, she will take exactly 8 hours:
Pile 1: ceil (3/4) = 1 hour
Pile 2: ceil (6/4) = 2 hours
Pile 3: ceil (7/4) = 2 hours
Pile 4: ceil (11/4) = 3 hours
Total: 1 + 2 + 2 + 3 = 8 hours, which matches h = 8
Any speed slower than 4 would require more than 8 hours, so the answer is 4.Example 2:
Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation:
- If Koko eats at a speed of 30 bananas per hour, she will take exactly 5 hours:
* Pile 1: ceil(30 / 30) = 1 hour
* Pile 2: ceil(11 / 30) = 1 hour
* Pile 3: ceil(23 / 30) = 1 hour
* Pile 4: ceil(4 / 30) = 1 hour
* Pile 5: ceil(20 / 30) = 1 hour
- Total: 1 + 1 + 1 + 1 + 1 = 5 hours, which matches `h = 5`.
- Any speed slower than 30 would require more than 5 hours, so the answer is 30.Example 3:
Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Explanation:
- If Koko eats at a speed of 23 bananas per hour, she will take exactly 6 hours:
* Pile 1: ceil(30 / 23) = 2 hours
* Pile 2: ceil(11 / 23) = 1 hour
* Pile 3: ceil(23 / 23) = 1 hour
* Pile 4: ceil(4 / 23) = 1 hour
* Pile 5: ceil(20 / 23) = 1 hour
- Total: 2 + 1 + 1 + 1 + 1 = 6 hours, which matches `h = 6`.
- Any speed slower than 23 would require more than 6 hours, so the answer is 23.Example 4:
Input: piles = [7, 15, 6, 3], h = 8
Output: 5
Explanation:
If Koko eats 5 bananas/hr, It will takes
ceil(7/5) = 2
ceil(15/5) = 3
ceil(6/5) = 2
ceil(3/5) = 1
Total = 2 + 3 + 2 + 1 = 8 which is less than or equal to 8.Example 5:
Input: piles = [25, 12, 8, 14, 19], h = 5
Output: 25
Explanation:
If Koko eats 25 bananas/hr, it will takes
ceil(25/25) = 1
ceil(12/25) = 1
ceil(8/25) = 1
ceil(14/25) = 1
ceil(19/25) = 1
Total = 1 + 1 + 1 + 1 + 1 = 5, which is less than or equal to 5.Constraints:
- 1 ≤ n ≤ 10^4
- n ≤ h ≤ 10^9
- 1 ≤ nums[i] ≤ 10^9
Different Approaches
1️⃣ Linear Search
The straightforward solution for this problem is to use linear search algorithm to check all possible answers from 1 to max, where max is use the maximum element of the array. The number for which the required time is less than or equal to h, is our required answer.
Code:
#include <iostream>
#include <vector>
#include <climits> // for INT_MAX and INT_MIN
using namespace std;
// Function to find the minimum eating rate (bananas per hour)
// such that Koko can eat all bananas in 'h' hours.
int minimumRateToEatBananas(vector<int> nums, int h) {
// Initialize min and max to track the smallest and largest pile sizes
int min = INT_MAX;
int max = INT_MIN;
// Find the minimum and maximum values in the banana piles
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > max) {
max = nums[i]; // Update max if current pile is larger
}
if (nums[i] < min) {
min = nums[i]; // Update min if current pile is smaller
}
}
// Define the range for Koko's possible eating rates
int left = min; // Smallest eating rate (start at smallest pile)
int right = max; // Largest eating rate (start at largest pile)
// Iterate over possible eating speeds from 'left' to 'right'
for (; left <= right; left++) {
int sum = 0; // Total hours Koko would need at current eating rate 'left'
// Calculate total hours required to eat all piles at current speed 'left'
for (int i = 0; i < nums.size(); i++) {
// Equivalent to ceil(nums[i] / left)
sum += (nums[i] + left - 1) / left;
}
// Check if Koko can finish within 'h' hours at this rate
if (sum <= h) {
return left; // Return the minimum speed that allows Koko to finish on time
}
}
return -1; // If no feasible eating speed is found (though this case shouldn't happen)
}
int main() {
vector<int> nums = {3, 6, 7, 11}; // Banana piles
int h = 8; // Number of hours Koko has
// Output the minimum rate Koko needs to eat all bananas in 'h' hours
cout << minimumRateToEatBananas(nums, h);
return 0;
}
Complexity Analysis:
- Time Complexity:
O(max * N), wheremaxis the maximum element in the array andNis the size of the array. We are running nested loops. The outer loops runs for max times in the worst case and the inner loop runs forNtimes. - Space Complexity:
O(1)As no additional space is used.
2️⃣ Binary Search
Intuition:
The idea here is to use binary search algorithm to solve this problem in a optimized way. Now, the search space will be in the range [1,max], where max is the maximum element in the array because the maximum bananas that the monkey can it per hour can be the maximum element of the array. As, the search space is sorted so binary search can be applied for better time complexity.
Dry Run:
+-----+-----+-----+-----+
nums = | 3 | 6 | 7 | 11 |
+-----+-----+-----+-----+
h = 8First Iteration:
+-----+-----+-----+-----+
nums = | 3 | 6 | 7 | 11 |
+-----+-----+-----+-----+
h = 8
left = 1
right = max(nums) = 11
mid = left + (right - left) / 2
= 1 + (11 - 1) / 2 = 1 + 5 = 6
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^ ^
| | |
left mid right
Total hours spent at rate of mid:
= ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6)
= 1 + 1 + 2 + 2
= 6
As total hours <= h
6 <= 8
// Go left as it would increase the total hours
set right = mid - 1
right = 6 - 1
= 5Second Iteration:
+-----+-----+-----+-----+
nums = | 3 | 6 | 7 | 11 |
+-----+-----+-----+-----+
h = 8
left = 1
right = 5
mid = left + (right - left) / 2
= 1 + (5 - 1) / 2 = 1 + 2 = 3
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^ ^
| | |
left mid right
Total hours spent at rate of mid:
= ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3)
= 1 + 2 + 3 + 3
= 9
As total hours > h
9 > 8
// Go right as it would decrease the total hours
set left = mid + 1
left = 3 + 1
= 4Third Iteration:
+-----+-----+-----+-----+
nums = | 3 | 6 | 7 | 11 |
+-----+-----+-----+-----+
h = 8
left = 4
right = 5
mid = left + (right - left) / 2
= 4 + (5 - 4) / 2 = 4 + 0 = 4
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
| |
left right
mid
Total hours spent at rate of mid:
= ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4)
= 1 + 2 + 2 + 3
= 8
As total hours <= h
8 <= 8
// Go left as it would increase the total hours
set right = mid - 1
right = 4 - 1
= 3Loop Termination:
+-----+-----+-----+-----+
nums = | 3 | 6 | 7 | 11 |
+-----+-----+-----+-----+
h = 8
left = 4
right = 3
As left exceeded the right, the loop will terminate here.
And left variable contains our answer, return it.
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
F F F T T T T T T T T
^ ^
| |
right left
Code:
#include <iostream>
#include <vector>
#include <climits> // for INT_MAX and INT_MIN
using namespace std;
// Function to determine the minimum rate (bananas per hour) Koko needs to finish all bananas within 'h' hours
int minimumRateToEatBananas(vector<int> nums, int h) {
// Initialize max values to find the maximum in the array
int max = INT_MIN;
// Find the minimum and maximum banana count in the piles
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > max) {
max = nums[i];
}
}
// Use binary search over possible eating speeds
int left = 1; // Minimum possible speed (Koko can eat at least 1 banana per hour)
int right = max; // Maximum speed (Koko could potentially eat the largest pile in one hour)
// Binary search to find the minimum feasible eating speed
while (left <= right) {
int mid = left + (right - left) / 2; // Midpoint of current search range
int hoursSpent = 0;
// Calculate total hours needed at the current eating speed 'mid'
for (int bananas : nums) {
hoursSpent += (bananas + mid - 1) / mid; // Equivalent to ceil(bananas / mid)
}
// Check if the current speed allows Koko to finish within 'h' hours
if (hoursSpent <= h) {
// If so, it could be the answer, but we check for a smaller rate
right = mid - 1;
} else {
// If it takes too long, we need a higher eating rate
left = mid + 1;
}
}
// 'left' will hold the minimum feasible eating speed after binary search
return left;
}
int main() {
vector<int> nums = {3, 6, 7, 11};
int h = 8;
cout << "Minimum rate to eat all bananas in " << h << " hours: " << minimumRateToEatBananas(nums, h) << endl;
return 0;
}OR
class Solution {
public:
// Function to find the minimum eating rate (bananas per hour)
// so that Koko can finish all bananas within 'h' hours
int minimumRateToEatBananas(vector<int> nums, int h) {
// Find the maximum number of bananas in any single pile (upper bound of Koko's eating rate)
int max = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > max) {
max = nums[i];
}
}
// Initialize binary search bounds
int left = 1; // Smallest possible eating speed
int right = max; // Largest possible eating speed (eating the largest pile in one hour)
int ans = 0; // Variable to store the minimum feasible eating rate
// Binary search over possible eating rates
while (left <= right) {
int mid = left + (right - left) / 2; // Midpoint of current search range
int totalHours = 0; // Total hours Koko would need at eating rate 'mid'
// Calculate the total hours required to eat all piles at the current speed 'mid'
for (int i = 0; i < nums.size(); i++) {
// Calculate time to eat current pile at rate 'mid'
// (nums[i] + mid - 1) / mid performs integer ceiling division
totalHours += (nums[i] + mid - 1) / mid;
}
// Check if the current speed allows Koko to finish within 'h' hours
if (totalHours <= h) {
// If it works, try for a smaller rate by moving left
ans = mid; // Update answer to current mid as it meets the condition
right = mid - 1; // Move search to the left to check for smaller feasible rates
} else {
// If it takes too long, try a faster rate by moving right
left = mid + 1;
}
}
// Return the minimum feasible eating rate
return ans;
}
};
Complexity Analysis:
- Time Complexity:
O(N * log(max)), wheremaxis the maximum element in the array andNis size of the array. We are applying binary search for the range[1, max], and for every value ofmid, we are traversing the entire array. - Space Complexity:
O(1).
Tricks Used:
Finding the Ceil of integers:
1️⃣ Using the formula:
The most efficient way is to use the manual formula:
ceil of a / b = (a + b - 1) b
int ceilValue = (a + b - 1) / b;
2️⃣ Using Floating-Point Arithmetic:
Convert one operand to a floating-point type, divide, and use the ceil from <cmath>:
#include <cmath>
int ceilValue = ceil(static_cast<double>(a) / b);
Example:
int count = 0;
for (int i = 0; i < piles.size(); i++) {
count += ceil(static_cast<double>(piles[i]) / speed);
}3️⃣ Using Integer Logic
You can mimic the ceiling behavior using a loop (not efficient but intuitive):
int ceilValue = a / b;
if (a % b != 0) {
ceilValue++;
}
Example:
int count = 0;
for (int i = 0; i < piles.size(); i++) {
count += (piles[i] / speed);
if (piles[i] % speed != 0) {
count++;
}
}