Last Updated: 2 Feb, 2023

Koko Eating Bananas

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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):

Int n is the number of piles of bananas.
Declare two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively.
Initialize a variable ‘ans’, which will store our final answer.
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’
Return ‘ans’.

Solve now