 # How to solve toffee boxes problem ?

I have seen this problem recently and it was asked in directi hiring challenge.

You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

You can only choose consecutive toffee packets to put in a box.

Input

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, M denoting the number of toffee packets and the number of boxes respectively. The second line of each test case contains N space separated integers c1, c2, …, cN where ci denotes the number of the toffees in the ith toffee packet.

Output

For each test case, output a single line containing the maximum number of toffees in a box. Also, output -1 if such an assignment of toffee packets to boxes is not possible.

Constraints

1 ≤ T ≤ 20
1 ≤ N,K ≤ 100000
1 ≤ ci ≤ 1000

Example

Input:
1
4 2
10 3 5 7

Output:
13

Explanation

Below are the possible assignments of toffee packets to boxes.

10 [3 5 7]
10 3 [5 7]
10 3 5 
For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13

I am not able to get any idea how to solve this.Please suggest a solution so that i can understand.

10 3 5 7 

1 Like

Apply binary search over the search space. Here Ci <= 10^3, so the highest value which can be the answer is high = (10^5 * 10^3 = 10^8)…Similarilly, lower bound can be 0…Now apply binary search over this space and each time go to left or right of mid depending upoun if a combination is possible with the given constraints. Each possibility can be verified in o(n) time and binary search will not ask for answers for > log(10^8) possibilites…thus the complexity becomes O(n*logn) per test case

1 Like

Thanks sandeep bro, for reply. +1… its what exactly I applied for hotstar too. It works. Thanks again for the reply.

1 Like

As you said “Each possibility can be verified in o(n) time”. How this is the problem? I got stuck here.