2
$\begingroup$

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

  • 1
    This doesn't seem like a research-level question. Please read the FAQ.2011-07-12
  • 1
    Seems like a homework problem. We don't do those.2011-07-13
  • 1
    I'm not sure I know the answer, even though it seems like a cute puzzle.2011-07-13
  • 0
    @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 :).2011-07-14
  • 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.2011-07-14

1 Answers 1

3

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.

  • 0
    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)$.2011-07-15
  • 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.2011-07-15
  • 0
    @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).2011-07-15
  • 0
    @Kaveh: I believe that one can find the $i$th median in linear time, so reduction in this direction won't help.2011-07-16
  • 0
    @Yuval, I thought that's only when i is fixed and not part of the input, should check CLRS.2011-07-16
  • 1
    @Kaveh: In fact, it seems that you can do it in $O(n)$ even in this case.2011-07-17
  • 0
    @Yuval, nice. :)2011-07-18