0

Ninja And Chocolates

Difficulty: MEDIUM
Contributed By
Prateek Kalyani
Avg. time to solve
20 min
Success Rate
80%

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
Sample Input 1 :
1
4 10
5 4 3 2 
Sample Output 1 :
 2
Explanation of Sample Input 1 :
If Ninja eats at a speed of 2 chocolates per minute, he can finish before his mother comes back. There are many ways in which he can eat these chocolates. One such way is that he takes 3 minutes to eat all the chocolates(5) from 1st Jar, 2 minutes to eat all the chocolates(4) from the 2nd Jar,  2 minutes to eat all the chocolates(3) from 3rd Jar, and finally, take 1 minute to eat all the chocolates from the final jar which has 2 chocolates. The total time taken will be 3+2+2+1 = 8 which is less than 10.
Sample Input 2 :
1
5 5
3 9 3 4 4
Sample Output 2 :
9
Explanation of Sample Input 2 :
If Ninja eats at a speed of 9 chocolates per minute, he can finish before his mother comes back. One such way is that he can start eating chocolates from the 2nd jar and take 1 minute to eat all the 9 chocolates from that jar and 1 minute each for all other jars since each jar has less than 9 chocolates. Hence, the total time will be 1+1+1+1+1 = 5, which is just in time.
Reset Code
Full screen
copy-code
Console