Sponsored
Sponsored
Since the constraint for hours is very large, a direct approach may not work efficiently. Instead, we can use binary search on the possible eating speeds (from 1 to the maximum value in the piles) to find the minimum speed at which Koko can eat all the bananas in the allotted time. For a given speed, compute the number of hours Koko would need to eat all the bananas.
Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. Space Complexity: O(1), as the additional space used by the algorithm does not depend on input size.
1#include <vector>
2#include <algorithm>
3using namespace std;
4int minEatingSpeed(vector<int>& piles, int h) {
5 int left = 1, right = *max_element(piles.begin(), piles.end());
6 while (left < right) {
7 int mid = left + (right - left) / 2;
8 int hours = 0;
9 for (int pile : piles) {
10 hours += (pile + mid - 1) / mid;
11 }
12 if (hours <= h) right = mid;
13 else left = mid + 1;
14 }
15 return left;
16}This C++ solution employs a binary search strategy on the speed to find the minimum feasible speed. It calculates the total hours required to consume all bananas using the mid value as the speed, updating the left or right boundary based on the feasibility check.
In this approach, we iterate over every possible eating speed from 1 to the maximum pile size and check if Koko can finish eating all within h hours. Although inefficient for large inputs, it works correctly for smaller constraints but mainly serves as a fallback understanding of the problem dynamics.
Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: O(1).
1class Solution:
2 def minEatingSpeed(self, piles, h):
3The brute force Python solution iteratively checks each potential speed and calculates the total hours required with a direct loop comparison. It returns the first speed that allows completing all piles within the time limit.