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
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.
How will we apply binary search?
I think it's the same as this problem?
I could not understand the editorial so I was looking for alternate method or better explanation of the given method.
You might want to look at this post first. Subset sum DP is possible in O(NsqrtN).