Hello coders!
Problem statement
Given an integer array, the values of the array need to separated into two subsets A and B whose intersection is null and whose unions the entire array. The sum of values in set A must be strictly greater than sum of values in set B, and number of elements in set A must be minimal. Return the values in set A.
Example explanation:
For eg. Given arr ={3,7,5,6,2}, here A would be {6,7}. Given arr = {2,3,4,4,5,9,7,8,6,10,4,5,10,10,8,4,6,4,10,1}, here A would be {8, 8, 9, 10, 10, 10, 10}.
Constraints:
1<=n<=10^5
1<=arr[i]<=10^5
UPD: Problem link. But the given solution is O(n*n) in the worst case and I want to solve it in less than O(n*n)
Ahh, sure, depends but you can just sort and keep on taking numbers from the end till the sum is greater than the sum of the remaining numbers.
This is a simple sorting problem, why do u want to use binary search here?
I think you forgot to read this line in the statement:
whose intersection is null
so in case of duplicates simple sorting will fail.
e.g.: [2, 5, 5, 9]
we can't take {5, 9} here because intersection with remaining set won't be null after.
I see, so one needs to take every equal element in one set
I think you can basically just sum all equal elements into a single element, and in the transformed array, perform the usual sort and take things from the end like I mentioned at the top
Illustration
For eg-[5, 5, 2, 2, 9]->[5+5, 2+2, 9]->[10, 4, 9] Then perform the usual sorting and take things from the end
Ok, but what about:
number of elements in set A must be minimal
Oops. You just commented with another account
I don't know that guy in any way. I just wanted to help.
Just guessing but likely knapsack can be reduced to it and I am not sur if there is faster than O(NC) algorithm for knapsack