### silversRayleigh's blog

By silversRayleigh, history, 6 years ago,

Hello Everyone,

I was trying to solve a problem in which I was given a set of number(in range 1-10^5 and size of set is at max 10^5). Task was to form the two disjoint sets from the given set such that sum of elements of each set is at least X(in range 1-10^5) and sum of size of both sets is minimized.

I tried a lot but could only come up with O(n^2) solution. Can anyone please suggest some idea on how to do it?

Note : Union of disjoint sets need not be the original set.

TIA

• +2

 » 6 years ago, # |   +5 How about binary searching for the minimal sum of sizes? Clearly, if you can form such two sets with k elements, you can also form two such sets with the k largest elements in your set.
•  » » 6 years ago, # ^ |   0 How will we apply binary search?
 » 6 years ago, # |   +1 I think it's the same as this problem?
•  » » 6 years ago, # ^ |   0 I could not understand the editorial so I was looking for alternate method or better explanation of the given method.
•  » » » 6 years ago, # ^ |   +3 You might want to look at this post first. Subset sum DP is possible in O(NsqrtN).