Блог пользователя oobxw9zf0lm7ez

Автор oobxw9zf0lm7ez, история, 3 года назад, По-английски

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)

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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