Last Updated: 18 Feb, 2021

Ninja And Chocolates

Moderate

Asked in companies

Solve now

Problem statement

Ninja is hungry and wants to eat his favorite chocolates but his mother won’t let him eat since he has already eaten enough chocolates. There are ‘N’ jars filled with chocolates. His mother has gone to the market and will home come after ‘M’ minutes. The ninja can eat up to ‘X’ chocolates per minute. Every minute when his mother is not there, he chooses any jar and takes out ‘X’ chocolates from that jar, and eats them. If any jar has less than ‘X’ chocolates, then he eats all of the chocolates in that jar but won’t eat any more chocolates during this minute. Your task is to print ‘X’ the minimum chocolate-eating speed of Ninja such that he eats all the chocolates within ‘M’ minutes before his mother comes back.

Input Format :

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'M', the number of jars, and the minutes after which his mother comes back.

The second line of each test case contains 'N' space-separated integers, the number of chocolates present in 'N' jars.

Output Format:

For every test case, the only line of output should contain an integer 'X', the minimum chocolate-eating speed of Ninja as described in the problem statement. 

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <=  N <= 10^6
N <= M <= 10^9
1 <= chocolates[i] <= 10^9

Time limit: 1 sec

Solve now

Approaches

01 Approach

The brute force approach to this problem is that we continuously iterate on the speed of eating chocolates till Ninja can eat all the chocolates within ‘M’ Minutes.

Algorithm:

Make a variable ‘sum’, which will store the sum of all chocolates which are present in all N jars.
Now to find the starting speed, we’ll use the fact that our required speed has to be greater than the average speed(sum/M), else the Ninja won’t be able to finish all the chocolates, hence make an integer variable ‘speed’ = ceil(sum/M), where ceil will return the smallest integer that is greater than or equal to (sum/M). The maximum speed will be max(chocolates[i]).
Now run a while(true) loop.
1. Initialize an integer ‘currentMinute’ = 0, which will store the time to eat all the chocolates with current speed.
2. Run a loop(loop variable ‘i’) from 0 till N-1.
  1. For each ‘i’ do the operation, currentMinute = currentMinute + ceil((chocolates[i])/(speed)).
  2. After each operation check if currentMinute > M, if this is true exit this loop.
3. If currentMinute <= M, exit this while loop. The current speed will be the minimum speed to eat all the chocolates.
4. After all the above increment speed by 1.
After exiting the while loop, return speed.

Solve now

02 Approach

Since our search space(‘chocolates’) is very high, we can use binary search to efficiently find the minimum chocolate-eating speed. We can use the fact that if ‘X’ is the minimum eating speed, then every value which is larger than ‘X’ will also satisfy the condition.

Algorithm:

Make an integer variable ‘start’ = 1 and another variable ‘end’ which will be equal to the jar with the maximum chocolates.
Now, run a loop while start < end.
Make an integer variable mid = start + (end- start)/2 and initialize another variable ‘count’ = 0, which will store the time to eat all the chocolates with current speed(mid).
1. Run a loop(loop variable ‘i’) from 0 till N - 1.
  1. Do the operation, count = count + ceil((chocolates[i])/mid).
2. If count <= M(minutes), make end = mid, else start = mid + 1.
Return ‘start’.

Solve now