New update is available. Click here to update.

Last Updated: 18 Feb, 2021

Moderate

```
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.
```

```
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.
```

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

```
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