Koko Eating Bananas Solution for Accenture
Company: Accenture · Difficulty: Medium · Topics: Array, Binary Search, Greedy
Problem Statement
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 from any more piles during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer k such that she can eat all the bananas within h hours.
Key Understanding:
- Koko must eat all bananas within h hours
- Each hour, she can eat from one pile only
- If a pile has fewer bananas than her speed k, she eats all remaining bananas from that pile
- We need to find the minimum speed k that allows her to finish in time
- Koko wants to eat as slowly as possible (minimum k)
Examples
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation:
- If k = 4:
- Hour 1: Eat 4 from pile [3,6,7,11] → [3,6,7,7]
- Hour 2: Eat 4 from pile [3,6,7,7] → [3,6,7,3]
- Hour 3: Eat 4 from pile [3,6,7,3] → [3,6,7,0]
- Hour 4: Eat 4 from pile [3,6,7,0] → [3,6,3,0]
- Hour 5: Eat 4 from pile [3,6,3,0] → [3,6,0,0]
- Hour 6: Eat 4 from pile [3,6,0,0] → [3,2,0,0]
- Hour 7: Eat 4 from pile [3,2,0,0] → [3,0,0,0]
- Hour 8: Eat 3 from pile [3,0,0,0] → [0,0,0,0]
- Total time: 8 hours ✓
- If k = 3: Would take more than 8 hours ✗
- If k = 5: Would work but not minimum ✗
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation:
- If k = 30:
- Hour 1: Eat 30 from pile [30,11,23,4,20] → [0,11,23,4,20]
- Hour 2: Eat 30 from pile [0,11,23,4,20] → [0,0,23,4,20]
- Hour 3: Eat 30 from pile [0,0,23,4,20] → [0,0,0,4,20]
- Hour 4: Eat 30 from pile [0,0,0,4,20] → [0,0,0,0,20]
- Hour 5: Eat 30 from pile [0,0,0,0,20] → [0,0,0,0,0]
- Total time: 5 hours ✓
- If k = 29: Would take more than 5 hours ✗
Example 3:
Input: piles = [312884470], h = 312884469
Output: 2
Explanation:
- With k = 2, it takes 312884470/2 = 156442235 hours
- But we only have 312884469 hours, so k = 2 is too slow
- With k = 1, it takes 312884470 hours, which is more than available time
- Therefore, no solution exists with k < 2
Intuition
The key insight is to use binary search to find the minimum speed k. We can check if a given speed k is feasible by calculating how many hours it would take to eat all bananas.
Binary Search Approach:
- The minimum possible speed is 1 (eat 1 banana per hour)
- The maximum possible speed is max(piles) (eat the largest pile in 1 hour)
- For any speed k, we can calculate the total time needed
- If total time ≤ h, k is feasible; otherwise, k is too slow
Why Binary Search Works:
- If speed k is feasible, then any speed > k is also feasible
- If speed k is not feasible, then any speed < k is also not feasible
- This monotonic property allows us to use binary search
Approach
Approach 1: Binary Search (Optimal)
Algorithm:
1. Set left = 1, right = max(piles)
2. While left < right:
- mid = (left + right) / 2
- Calculate hours needed for speed mid
- If hours ≤ h: right = mid (try smaller speed)
- Else: left = mid + 1 (try larger speed)
3. Return left
Hours Calculation:
- For each pile, hours = ceil(piles[i] / k)
- Total hours = sum of all pile hours
Approach 2: Linear Search
Algorithm:
1. Try each speed from 1 to max(piles)
2. For each speed, calculate total hours needed
3. Return the first speed that works
Approach 3: Mathematical Approach
Algorithm:
1. Calculate total bananas = sum(piles)
2. Minimum speed = ceil(total_bananas / h)
3. Verify this speed works, if not, increment
Dry Run
Let's trace through Example 1: piles = [3,6,7,11], h = 8
Binary Search Approach:
- left = 1, right = 11 (max of piles)
- mid = 6
- Hours for speed 6: ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6) = 1 + 1 + 2 + 2 = 6
- 6 ≤ 8, so right = 6
- mid = 3
- Hours for speed 3: ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10
- 10 > 8, so left = 4
- mid = 5
- Hours for speed 5: ceil(3/5) + ceil(6/5) + ceil(7/5) + ceil(11/5) = 1 + 2 + 2 + 3 = 8
- 8 ≤ 8, so right = 5
- mid = 4
- Hours for speed 4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8
- 8 ≤ 8, so right = 4
- left = 4, right = 4, loop ends
- Return 4
Key Insights
1. Binary Search Range: Speed ranges from 1 to max(piles)
2. Monotonic Property: If speed k works, any speed > k also works
3. Hours Calculation: Use ceiling division for each pile
4. Optimal Solution: Binary search finds the minimum feasible speed
5. Edge Cases: Handle cases where no solution exists
Edge Cases
1. Single Pile: Only one pile of bananas
2. Large Piles: Very large numbers in piles
3. Minimum Hours: h = number of piles (must eat one pile per hour)
4. Maximum Hours: h = sum of all piles (can eat 1 banana per hour)
5. No Solution: When it's impossible to finish in time
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Binary Search (Optimal)
Time Complexity: O(n * log M) where n is number of piles and M is max pile size
Space Complexity: O(1) - Constant extra space
Solution 2: Linear Search
Time Complexity: O(n * M) where M is max pile size
Space Complexity: O(1) - Constant extra space
Solution 3: Mathematical Approach
Time Complexity: O(n) - Single pass through piles
Space Complexity: O(1) - Constant extra space