Koko Eating Bananas

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
192 upvotes
Asked in companies
AtlassianTennrUnthinkable Solutions LLP

Problem statement

A monkey is given ‘n’ piles of bananas, where the 'ith' pile has ‘a[i]’ bananas. An integer ‘h’ is also given, which denotes the time (in hours) in which all the bananas should be eaten.


Each hour, the monkey chooses a non-empty pile of bananas and eats ‘m’ bananas. If the pile contains less than ‘m’ bananas, then the monkey consumes all the bananas and won’t eat any more bananas in that hour.


Find the minimum number of bananas ‘m’ to eat per hour so that the monkey can eat all the bananas within ‘h’ hours.


Example:

Input: ‘n’ = 4, ‘a’ =  [3, 6, 2, 8] , ‘h’ = 7

Output: 3

Explanation: If ‘m’ = 3, then 
The time taken to empty the 1st pile is 1 hour.
The time taken to empty the 2nd pile is 2 hour.
The time taken to empty the 3rd pile is 1 hour.
The time taken to empty the 4th pile is 3 hour.
Therefore a total of 7 hours is taken. It can be shown that if the rate of eating bananas is reduced, they can’t be eaten in 7 hours.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains one integer, ‘n’, denoting the number of piles of bananas.

The second line contains ‘n’ integers denoting the number of bananas on the ith pile.

The third line contains one integer, ‘h’, denoting the time (in hours) in which all bananas should be eaten.


Output format: 
Return the minimum number of bananas (‘m’) to eat per hour so the monkey can eat all the bananas within ‘h’ hours.


Note: 
You don't need to print anything. Just implement the given function.
Sample Input 1:
4
7 15 6 3
8


Sample Output 1:
5


Explanation Of Sample Input 1:
Input: ‘n’ = 4, ‘a’ = [7, 15, 6, 3], ‘h’ = 8

Output: 5

Explanation: If ‘m’ = 5, then 
The time taken to empty the 1st pile is 2 hour.
The time taken to empty the 2nd pile is 3 hour.
The time taken to empty the 3rd pile is 2 hour.
The time taken to empty the 4th pile is 1 hour.
Therefore a total of 8 hours is taken. It can be shown that if the rate of eating bananas is reduced, they can’t be eaten in 8 hours.


Sample Input 2:
5
25 12 8 14 19
5


Sample Output 2:
25


Explanation Of Sample Input 2:
Input: ‘n’ = 5, ‘a’ = [25,12,8,14,19], ‘h’ = 5

Output: 25

Explanation: If ‘m’ = 25, 
The time taken to empty the 1st pile is 1 hour.
The time taken to empty the 2nd pile is 1 hour.
The time taken to empty the 3rd pile is 1 hour.
The time taken to empty the 4th pile is 1 hour.
The time taken to empty the 5th pile is 1 hour.
Therefore a total of 5 hours is taken. It can be shown that if the rate of eating bananas is reduced, they can’t be eaten in 5 hours.


Expected Time Complexity:
Try to solve the problem in O(log n).


Constraints:
1 <= n <= 10^4
1 <= a[i] <= 10^9
n <= h <= 10^9

Time Limit: 1 sec
Hint

Apply Binary Search on the eating rate of bananas per hour.

Approaches (1)
Binary Search

We will use Binary Search here. We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively. When applying the binary search algorithm, suppose we find the ‘mid’ as ‘(s + e) / 2’. Now, we will find out whether it is possible to eat all the bananas if the rate to eat them is ‘mid’. This can be found using the following way. We can iterate through the array of piles, and to find how many hours will be required to eat a particular pile (say the number of bananas in this pile is ‘p’), we can find the ‘ceil value’ or the minimum number which is perfectly divisible by ‘mid’ and is greater than or equal to ‘p’. If, for the current ‘mid’, the time taken to eat all bananas is less than or equal to ‘H’, this means ‘mid’ can be our final answer, but we would look for smaller answers. Otherwise, we would look for some bigger answers.

 

The steps are as follows:-
 

// Function to find Minimum rate to Eat Bananas

function minimumRateToEatBananas(int n, int[] a, int h):

  1. Int n is the number of piles of bananas.
  2. Declare two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively.
  3. Initialize a variable ‘ans’, which will store our final answer.
  4. While s <= e:
    • Initialize a variable ‘mid’ and assign it to ‘(s + e) / 2’.
    • Initialize a variable ‘cnt’, which will store the hours taken to eat all the bananas if the rate to eat them is ‘mid’.
    • Iterate over the array a:
      • Initialize a variable ‘p’, which stores the number of bananas in the current pile.
      • Add ‘ceil value’ or (p + mid - 1) / mid to ‘cnt’.
    • If cnt <= h:
      • Make ‘ans’ equal to ‘mid’.
      • Make ‘e’ equal to ‘mid - 1’
    • Else:
      • Make ‘s’ equal to ‘mid + 1’
  5. Return ‘ans’.
Time Complexity

O( N * logM ), where N is the number of piles, and M is the integer(1e9).

 

We are traversing over the array ‘A’ at most logM times.

 

Hence the time complexity is O( N * logM ).

Space Complexity

O( 1 ).
 

We store our answers and other things in 2-3 variables.

 

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Koko Eating Bananas
Full screen
Console