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 <stdio.h>
2int minEatingSpeed(int* piles, int pilesSize, int h) {
3 int max = 0;
4 for (int i = 0; i < pilesSize; i++) {
5 if (piles[i] > max) max = piles[i];
6 }
7 int left = 1, right = max;
8 while (left < right) {
9 int mid = (right - left) / 2 + left;
10 int hours = 0;
11 for (int i = 0; i < pilesSize; i++) {
12 hours += (piles[i] + mid - 1) / mid;
13 }
14 if (hours <= h) {
15 right = mid;
16 } else {
17 left = mid + 1;
18 }
19 }
20 return left;
21}The C solution uses a binary search to find the minimum eating speed. It first determines the maximum pile size, which sets the upper limit for the search range. A helper loop calculates the total number of hours needed if Koko eats at a particular speed, adjusting the search range based on whether the number of hours is within the allowed time.
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.