Koko, a monkey, loves bananas. She has a pile of banana stacks and wants to eat all of them within H hours. She can only eat a fixed number of bananas per hour. The goal is to determine the minimum eating speed (bananas per hour) that allows her to finish all the bananas on time.
This problem involves finding the optimal eating speed using binary search, making it both a fun and practical example of optimization techniques.
Brute Force Approach
In the brute force solution, we try every possible eating speed from 1 to the maximum number of bananas in a stack, calculating the total time required for each speed until we find the minimum speed that allows Koko to eat all the bananas in H hours.
public class KokoEatingBananas {
public int minEatingSpeed(int[] piles, int h) {
int maxPile = 0;
for (int pile : piles) {
maxPile = Math.max(maxPile, pile);
}
for (int speed = 1; speed <= maxPile; speed++) {
if (canEatAll(piles, h, speed)) {
return speed;
}
}
return -1; // Shouldn't reach here
}
private boolean canEatAll(int[] piles, int h, int speed) {
int hours = 0;
for (int pile : piles) {
hours += Math.ceil((double) pile / speed);
}
return hours <= h;
}
}Optimal Algorithm and Data Structure
Instead of testing all possible speeds, we can use binary search to find the minimum speed. The search range is from 1 (minimum possible speed) to the size of the largest pile (maximum possible speed). At each step, we check if the current speed allows Koko to eat all bananas on time. If yes, we try smaller speeds; if no, we try larger speeds.
Algorithm and Data Structure Pattern
• Binary Search: This problem is well-suited for binary search because the condition (“Can Koko eat all bananas within H hours?”) is monotonic. As speed increases, the time taken to eat all bananas decreases.
• Array Traversal: We traverse the banana piles to calculate the total time required for a given speed.
Why This Algorithm Works Well
• Efficient Search: Binary search reduces the search space exponentially, making it faster than brute force.
• Intuition: The problem’s monotonic nature ensures binary search is applicable, as once we find a speed that works, any higher speed will also work.
Steps of the Algorithm
1. Define the range of eating speeds: low = 1, high = max(piles).
2. Perform Binary Search:
• Calculate the mid-point speed.
• Check if Koko can eat all piles within h hours at this speed.
• If yes, search for slower speeds (high = mid – 1); otherwise, search for faster speeds (low = mid + 1).
3. Return the minimum speed that satisfies the condition.
public class KokoEatingBananas {
public int minEatingSpeed(int[] piles, int h) {
int low = 1, high = 0;
for (int pile : piles) {
high = Math.max(high, pile); // Find the largest pile size
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (canEatAll(piles, h, mid)) {
high = mid - 1; // Try smaller speeds
} else {
low = mid + 1; // Try larger speeds
}
}
return low; // Minimum speed to finish on time
}
private boolean canEatAll(int[] piles, int h, int speed) {
int hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed; // Faster ceiling division
}
return hours <= h;
}
}Line By Line Description
Step 1: Define Koko’s Eating Speed Range
int left = 1, right = Arrays.stream(piles).max().getAsInt();- Sets up the initial range for Koko’s possible eating speeds:
- left = 1: The slowest eating speed Koko could possible have is 1 banana per hour.
- right = max(piles): This is the fastest eating speed is the size of the largest pile.
Step 2: Perform Binary Search
while (left < right) {- Koko is testing different eating speeds to find the slowest one that lets her finish all the bananas on time. She starts by dividing her options in half.
Step 3: Test the Midpoint Speed
int mid = left + (right - left) / 2;- Koko picks a speed in the middle of her current range to see if it’s fast enough.
Step 4: Check If Koko Can Finish at Speed mid
if (canFinish(piles, h, mid)) {
right = mid;
} else {
left = mid + 1;
}• Calls canFinish to check if Koko can eat all the bananas within h hours at speed mid.
• If she can, right is set to mid to test even slower speeds.
• If she cannot, left is set to mid + 1 to test faster speeds.
Step 5: Return The Minimum Speed
return left;- After testing various speeds, Koko finds the slowest possible speed that still lets her finish all the bananas on time.
Step 6: Calculate Total Hours for a Given Speed
private boolean canFinish(int[] piles, int h, int speed) {
int hours = Arrays.stream(piles)
.map(pile -> (pile + speed - 1) / speed)
.sum(); // Sum up the hours
return hours <= h;
}- This helper function determines whether a given speed is fast enough for Koko to finish all piles on time.
- Koko calculates how long it will take to finish all the piles at her current speed and checks if it’s within her time limit.
- We need to calculate how many full hours koko requires to eat a pile of bananas at a given speed
- If koko can eat up to speed bananas in one hour, then for a pile of size pile, the hours required to finish it are:
Why the Code Was Written This Way
• Binary Search: Efficiently narrows down the possible speeds instead of testing every single one.
• Integer Arithmetic: Avoids floating-point operations for simplicity and precision.
• Clear Bounds: Ensures that the search always converges to a valid speed.
• Readable Logic: The if-else structure cleanly separates the cases for adjusting the range.
This approach guarantees an optimal solution in logarithmic time, which is far more efficient than a brute-force search.
