oobxw9zf0lm7ez's blog

Can binary search be used in this problem?
By oobxw9zf0lm7ez, history, 3 years ago, In English

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)

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a simple sorting problem, why do u want to use binary search here?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok, but what about:

        number of elements in set A must be minimal

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oops. You just commented with another account

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't know that guy in any way. I just wanted to help.

            → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply