Take the 2-minute tour ×

Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?

The minimum set will be a set with 1 element. Don't we just have to traverse the array and find an element i.e. >= K.

Otherwise for O(nlgn), I understand we have to first sort the array and then we can find pair or triplets which sum >=k. What if we don't find such a combination and have to go for bigger sets won't this problem be same as N sum problem?

share|improve this question
is this homework ? –  Pavan Yalamanchili Jan 21 '13 at 2:02
@Pavan..No it isn't ..It's an interview question..unfortunately I'm not getting "interview" tag anymore so couldn't tag it. –  user1071840 Jan 21 '13 at 2:23

2 Answers 2

up vote 4 down vote accepted

Here's a linear algorithm that uses linear-time median finding as a subroutine:

Findsum(A, K) {
  Let n be the length of A.
  Let M be the median element of A, found in linear time.
  Let L be the elements of A less than M.
  Let U be the elements of A greater than M.
  Let E be the elements of A equal to M.
  If the sum of the elements in U is at least K,
    Return Findsum(U, K).
  Else, if the sum of the elements in U and E is at least K,
    Return U together with enough elements of E that the sum is at least K.
    Return Findsum(L, K - sum(U) - sum(E)).

Each recursive call is done on a list at most half the size of A and all other steps take at most linear time, so this algorithm takes linear time overall.

share|improve this answer
Are you sure that's a linear algorithm? –  xpda Jan 21 '13 at 2:58
Yes. You get a recurrence that looks like T(n) <= T(n/2) + c*n, which gives you the bound T(n) <= 2*c*n. –  tmyklebu Jan 21 '13 at 3:06
You get the job! –  xpda Jan 21 '13 at 3:22
Nice, but didn't you mean M instead of A[i] in the definitions of L, U, and E? –  Gene Jan 21 '13 at 3:40
@Gene: Yeah, thanks. –  tmyklebu Jan 21 '13 at 3:47

This is very different from the N Sum problem because it requires the set add up to at least K instead of exactly K.

It can be done in O(n ln n) by sorting the list and progressing from the maximum element until the sum is greater than K. It can be optimized by scanning the list first to eliminate the case where a single number > K and the case where the sum of all members < K. You could also get the average value of the list, and, sometimes, only sort the "upper" half of the list. These optimizations don't improve the O(n ln n) time, though.

The sorting can be done using an index array (or list of integers), so the original values or objects don't need to be moved.

share|improve this answer

Your Answer


