You are not logged in. Please login at to post your questions!


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.


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.


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.


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


Input: 1 4 2 10 3 5 7

Output: 13


Below are the possible assignments of toffee packets to boxes.

10 [3 5 7] 10 3 [5 7] 10 3 5 [7] 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.

asked 28 Jul '16, 11:50

anu1234's gravatar image

accept rate: 0%

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


answered 28 Jul '16, 12:28

sandeep9's gravatar image

accept rate: 4%

edited 28 Jul '16, 12:29

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

(28 Jul '16, 15:47) anu12341★

Say for your test case we need to pack(10,3,5,7) in 2 boxes..for any possibility say k = 10, we will start picking toffees from left and fill each box(in this case 2) until it can be filled with <= 10 toffee,after processing all toffees,if a box remained empty or there are toffees left but our bags are already full then it implies that we cannot have 10 as our we will then check for values > 10..and so on..similarilly, if at sometime the configuration is possible we will search for lower values than our current value..

(28 Jul '16, 16:34) sandeep93★

ok i got your idea , do you think this solution will pass in 1 second time limit ?

(29 Jul '16, 09:48) anu12341★

yes,much less than that

(29 Jul '16, 21:31) sandeep93★

ok thank you

(30 Jul '16, 09:33) anu12341★

10 3 5 7 [57]


answered 28 Jul '16, 12:16

balaji_goud's gravatar image

accept rate: 0%


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


answered 28 Jul '16, 15:00

noor7300's gravatar image

accept rate: 0%

please do not spam

(28 Jul '16, 16:06) anu12341★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 28 Jul '16, 11:50

question was seen: 4,535 times

last updated: 30 Jul '16, 09:33