Ninja And Chocolates

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in companies
FacebookSalesforceD.E.Shaw

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Hint

Iterate on eating-speed to find minimum eating-speed.

Approaches (2)
Brute Force

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:

  1. Make a variable ‘sum’, which will store the sum of all chocolates which are present in all N jars.
  2. 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]).
  3. 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.
  4. After exiting the while loop, return speed.
Time Complexity

O(N*max(chocolates[i])), where ‘N’ is the number of jars and ‘max(chocolate[i])’ is the jar with the maximum number of chocolates.

 

In the worst case, the maximum number of times our while loop can run is max(chocolates[i]) times which will cost us O(max(chocolates[i])) time, and each time inside this loop we’ll traverse our chocolate array of size N which will cost us O(N) time. Hence, total complexity will be O(N*max(chocolates[i])).

Space Complexity

O(1)

 

As we are using constant memory space.

Code Solution
(100% EXP penalty)
Ninja And Chocolates
Full screen
Console