Count ordered pairs of disjoint subsets having sum greater than K

help
, ,
1

You are given an array A[] having N elements and a number K. You have to count ordered pairs of disjoint non-empty subsets each having a sum greater than K.

For example:

N=3 and K=5
A = {3, 4, 7}

Then the answer will be 2.
i.e., ({3,4}, {7}) and ({7}, {3,4})

How can I solve this optimally?

1 Like
3

If I am not wrong, We can do it in nlogn time.
We first sort the array. Then we make a prefix sum array named pre. We then take two pointers i pointing to first element of prefix sum array and j pointing to the last element of array.

  • If pre[i] + arr[j] <= k then we increment i by 1. Why? as all the elements before j will also have non-positive sum with the ith element.
  • Also if pre[i] + arr[j] > k We add powers of 2 starting from 2^i to 2^(j -1) to our answer and we decrement j by 1. Why? ’cause all the elements after ith element will also give positive sum with the jth element.
    We do this until i == j.
    P.S - Correct me if I’m wrong.
1 Like
4

powers of 2 starting from 2^i to 2^(j -1) is just 2^j - 2^i using geometric sum

5

That’s clever. But it counts only the subsets having sum greater than k. I need to find the ordered pair of such subsets.

6

It counts Ordered subsets actually

7

For the given example, your algorithm produces ouput as 4. Whereas the actual answer is 2.

1 Like
8

@karthickshiva , lets take a sorted array i.e {2,4,7,10,12,15} and k = 5 , now the answer for this is 5 right? , subset {7},{10},{12},{15},{2,4}… could you please clarify my doubt?
or is it like counting the pairs? like
{7,10},{12,15},{2,4}
{7,15},{4,12},{2,10} … and so on

9

You have to count like this:

({2,4}, {7,10,12,15})
({2,7}, {4,10,12,15})
({2,10}, {4,7,12,15})
({2,12}, {4,10,7,15})
({2,15}, {4,10,12,7})

({4,7}, {2,10,12,15})
({4,10}, {2,7,12,15})
({4,12}, {2,10,7,15})
({4,15}, {2,10,12,7}) and so on…

1 Like