Problem of the day
New update is available. Click here to update.
Last Updated: 18 Feb, 2021
Ninja And Chocolates
Moderate
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
Approaches
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.
- Initialize an integer βcurrentMinuteβ = 0, which will store the time to eat all the chocolates with current speed.
- Run a loop(loop variable βiβ) from 0 till N-1.
- For each βiβ do the operation, currentMinute = currentMinute + ceil((chocolates[i])/(speed)).
- After each operation check if currentMinute > M, if this is true exit this loop.
- If currentMinute <= M, exit this while loop. The current speed will be the minimum speed to eat all the chocolates.
- After all the above increment speed by 1.
- After exiting the while loop, return speed.
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).
- Run a loop(loop variable βiβ) from 0 till N - 1.
- Do the operation, count = count + ceil((chocolates[i])/mid).
- If count <= M(minutes), make end = mid, else start = mid + 1.
- Run a loop(loop variable βiβ) from 0 till N - 1.
- Return βstartβ.
Similar problems
Download our app:
FOLLOW US ON
We accept payments using:
