# Smallest subsequence with desired sum of complexity n and n logn

Given a sequence of integers ( +ve and/or -ve) $A_1, A_2, \ldots, A_n$, I need to find the smallest subsequence $A_i,\ldots, A_j$ whose sum is at least M.

How would the algorithm for the same go if I need a complexity of $O(n\log n)$ or at-most $O(n)$?

-

## migrated from cstheory.stackexchange.comJul 14 '11 at 19:57

This question came from our site for theoretical computer scientists and researchers in related fields.

This doesn't seem like a research-level question. Please read the FAQ. – Kaveh Jul 12 '11 at 15:51
Seems like a homework problem. We don't do those. – Peter Boothe Jul 13 '11 at 3:09
I'm not sure I know the answer, even though it seems like a cute puzzle. – Suresh Venkat Jul 13 '11 at 22:24
@Suresh, it doesn't seem difficult to me, it seems to me can be done in one pass over the sequence (or maybe I am missing something :). – Kaveh Jul 14 '11 at 0:49
How do you define subsequence? Is it $A_{i},A_{i+1}, A_{i+2}, \dots, A_j$ or is it $A_{i_1}, A_{i_2}, ..., A_{i_n}$? I am guessing the former. – Aryabhata Jul 14 '11 at 20:36

Consecutive case

Hint for $O(n\log n)$: calculate partial sums and use binary search.

Hint for $O(n)$: keep two pointers into the list and advance them alternately.

Non-consecutive case

Hint for $O(n\log n)$: sort the numbers and use binary search.

Hint for $O(n)$: find the median, calculate the sum of the upper half, and recurse on the appropriate half.

-
Both these solutions are for "subsequence" meaning a contiguous subsequence $A_i, A_{i+1}, \dots, A_j$, right? I tried to think of a solution to the problem where subsequence means $A_{i_1}, A_{i_2}, \dots$ as in the usual sense, but couldn't think of something that's $O(n)$. – ShreevatsaR Jul 15 '11 at 4:50
Right. For the other problem, there is a trivial $O(n\log n)$ solution by sorting. I'm not sure if you can do better. – Yuval Filmus Jul 15 '11 at 10:23
@ShreevatsaR, Yuval: in the nonconsecutive subsequence case, if $M$ is fixed and not part of the input, then we have a linear time algorithm since either there is a number larger than $M$ in which case we are done or all numbers are smaller in which case we can use a linear time sort. On the other hand, if $M$ is part of the input then I think the complexity should be similar to the i-th median problem (probably one can reduce the i-th median problem to this). – Kaveh Jul 15 '11 at 16:48
@Kaveh: I believe that one can find the $i$th median in linear time, so reduction in this direction won't help. – Yuval Filmus Jul 16 '11 at 21:58
@Kaveh: In fact, it seems that you can do it in $O(n)$ even in this case. – Yuval Filmus Jul 17 '11 at 21:13