How to generate k largest subset sums for a given array (contains positive and negative numbers)

user_16687488 0
Viewed 2190

So the question is pretty straight forward, given an array of size N( N<=10^5) , we want to generate k greatest subset sums where k is in worst case MIN of (2000 and 2^N).

We have to output in the decreasing order.

Is there any way to do this in less than exponential complexity. My thinking is that If we have to generate 2^N items , how can the complexity be less than 2^N,

Asked in amazon OA(question is called find k maximum priority)

algorithm
2 Answers

I'll just outline it. It is up to you to implement it and show that it works.

First, in a single pass, we find the sum of the positive numbers. This is the maximum sum. We initialize our answer array with [maximum_sum].

Next, we create an array av of the absolute values, sorted from smallest to largest.

Next, we create a priority queue upcoming. It will start with one pair in it. That pair will be (maximum_sum - av[0], 0). The pairs are compared lexicographically with largest sum first.

Until we have enough elements in answer we will:

get (next_sum, i) from upcoming
add next_sum to answer
if i < N:
    add (next_sum + av[i] - av[i+1], i+1) to upcoming
    add (next_sum - av[i+1], i+1) to upcoming

This algorithm will take O(N+k) memory and O(N log(N) + k log(k)) work to generate the top k answers. It depends on both N and k but is exponential in neither.

user_5854110

I will describe a bit simpler solution:

Let A be initial array, let Pos and Neg be sets of all positive (nonnegative, to be exact) and all negative numbers from A respectively.

Let us look at the problem from another point of view. Instead of choosing subsets from A and minimizing sums of both positive and negative numbers, we will consider an equivalent problem:

Take MaxSum := sum of all numbers in Pos. Clearly, this is the biggest possible sum we can get. Starting from MaxSum, we can get any subset sum of A by adding some numbers from Neg and subtracting some numbers from Pos. Note, that both operations subtract some nonnegative value from MaxSum! Thus, we’ve reduced our problem to a simpler one:

Simpler Problem: Take Abs := set of absolute values of Pos and Neg (<=> set of all absolute values of A). We need to choose k smallest sums from Abs to subtract from MaxSum.

Solution: Take smallest m, such that 2^m >= min(2^N, k). By the constrains of the problem we have m <= 11. Obviously, k smallest sums from Abs are some subsets of the smallest m numbers of Abs. Thus, we can consider all such 2^m <= 2048 subsets and get smallest sums (s_1, s_2, ... s_k). The final answer will be (MaxSum - s_1, MaxSum - s_2, ... MaxSum - s_k).

Time complexity:

  1. O(N) to find MaxSum
  2. O(N log(N)), for example, to find m smallest numbers from Abs. In fact, finding m smallest numbers can be done with O(N + m log(m)) complexity, see this. Since m <= 11, we can say that time complexity is also O(N).
  3. O(1) to consider 2^m <= 2048 sums from m numbers (using bit masks, for example).

Total time complexity: O(Nlog(N)) for straightforward approach and O(N) for optimized approach.

Space complexity: O(N + k) (<=> O(N), since k <= 2000).

user_93748920
Related