⬅ Previous Topic
Nth Root of a Number using Binary SearchNext Topic ⮕
Minimum Days to Make M Bouquets⬅ Previous Topic
Nth Root of a Number using Binary SearchNext Topic ⮕
Minimum Days to Make M BouquetsTopic Contents
Koko the monkey loves bananas. She has a list of banana piles, and she wants to eat all of them within h
hours. Each hour, Koko chooses any pile and eats up to k
bananas from it. If the pile has fewer than k
bananas, she eats the entire pile and moves on.
Your task is to help Koko determine the minimum integer eating speed k
such that she can finish all the bananas in at most h
hours.
If the list of banana piles is empty, return 0
as there are no bananas to eat.
low = 1
, high = max(piles)
, and answer = max(piles)
.low ≤ high
:mid = (low + high) / 2
as current eating speed.ceil(pile / mid)
.answer = mid
, and search left by setting high = mid - 1
.low = mid + 1
.answer
as the minimum valid eating speed.import math
def minEatingSpeed(piles, h):
low, high = 1, max(piles) # Possible eating speeds range from 1 to max pile
answer = high
while low <= high:
mid = (low + high) // 2
hours = sum(math.ceil(p / mid) for p in piles) # Total hours at speed 'mid'
if hours <= h:
answer = mid # Try a smaller speed
high = mid - 1
else:
low = mid + 1 # Need more speed to eat faster
return answer
# Example
print(minEatingSpeed([3, 6, 7, 11], 8)) # Output: 4
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n * log m) | Where n = number of piles, m = max(pile). Binary search over m with O(n) check each time. |
Average Case | O(n * log m) | Performs log(m) iterations of binary search with O(n) check per iteration. |
Worst Case | O(n * log m) | In worst case, binary search runs full range from 1 to max(pile), checking all piles each time. |
O(1)
Explanation: Only a constant number of variables are used for computation. No additional memory is required.
⬅ Previous Topic
Nth Root of a Number using Binary SearchNext Topic ⮕
Minimum Days to Make M BouquetsYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.