Find the minimum number of elements required so that their sum equals or exceeds S

Question

I know this can be done by sorting the array and taking the larger numbers until the required condition is met. That would take at least nlog(n) sorting time.

Is there any improvement over nlog(n).

We can assume all numbers are positive.

Answer 1

Here is an algorithm that is O(n + size(smallest subset) * log(n)). If the smallest subset is much smaller than the array, this will be O(n).

Read http://en.wikipedia.org/wiki/Heap_%28data_structure%29 if my description of the algorithm is unclear (it is light on details, but the details are all there).

1. Turn the array into a heap arranged such that the biggest element is available in time O(n).
2. Repeatedly extract the biggest element from the heap until their sum is large enough. This takes O(size(smallest subset) * log(n)).

This is almost certainly the answer they were hoping for, though not getting it shouldn't be a deal breaker.

Edit: Here is another variant that is often faster, but can be slower.

Walk through elements, until the sum of the first few exceeds S.  Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
    if min(in our heap) < element:
        insert element into heap
        increase current_sum by element
        while S + min(in our heap) < current_sum:
            current_sum -= min(in our heap)
            remove min from heap

If we get to reject most of the array without manipulating our heap, this can be up to twice as fast as the previous solution. But it is also possible to be slower, such as when the last element in the array happens to be bigger than S.