Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question

migrated from cstheory.stackexchange.com Jul 14 '11 at 19:57

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

1  
This doesn't seem like a research-level question. Please read the FAQ. –  Kaveh Jul 12 '11 at 15:51
1  
Seems like a homework problem. We don't do those. –  Peter Boothe Jul 13 '11 at 3:09
1  
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
1  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
1  
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.