Koko Eating Bananas
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the minimum eating speed to finish all banana piles within a given time (Koko Eating Bananas Problem), Arrays, Binary Search, Brute Force, Time Complexity, Space Complexity, Loops, Mathematical Algorithms, Functions, brute force, mathematical operations, greedy algorithm, binary search, time complexity analysis, Binary Search on Answer, Mathematical Operations.
Koko Eating Bananas Problem Statement A monkey named Koko loves to eat bananas. There are n piles of bananas, where the i th pile has a[i] bananas. You are also given an integer h, which denotes the total time (in hours) available for Koko to eat all the bananas. Each hour, Koko chooses a non empty pile of bananas and eats k bananas from it. If a pile contains less than k bananas, Koko eats all of them and does not eat any more bananas in that hour. Koko must finish eating all bananas within h hours. Find the minimum integer k (bananas per hour) such that Koko can eat all the bananas within h hours. Important Note on Eating: If a pile has X bananas and Koko eats k bananas per hour, the time taken to finish that pile is ceil(X / k) hours. For example, if Koko eats 2 bananas/hour and a pile has 3 bananas, it takes ceil(3/2) = 2 hours (1 hour for the first 2 bananas, and another hour for the remaining 1 banana). Input Specification An integer N, representing the number of piles. An array a[] of N integers, where a[i] is the number of bananas in the i th pile. An integer h, representing the total hours available. Output Specification Return the minimum integer k. Constraints 1 <= N <= 10^5 1 <= a[i] <= 10^9 N <= h <= 10^9 Sample Test Cases Example 1: Input: Output: Explanation: If Koko eats 5 bananas/hr, he will take 2, 3, 2, and 1 hour to eat the piles accordingly. So, he will take 2+3+2+1 = 8 hours to complete all the piles. Example 2: Input: Output: Explanation: If Koko eats 25 bananas/hr, he will take 1, 1, 1, 1, and 1 hour to eat the piles accordingly. So, he will take 1+1+1+1+1 = 5 hours to complete all the piles.