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 an array a[] of integers of arbitrary size N that sum to 0 (for example, a[] = {-1, 0, 5, 3, -9, 2}), does there always exists an index i ($0\le i\le N-1$) such that each partial sum $S_j = \sum_{k=i}^ j a_{k\pmod N}$ (with $N+i-1\ge j\ge i$) is nonnegative?

In the example a[] = {-1, 0, 5, 3, -9, 2} where $a_0 = -1, a_1 = 0, ... a_5 = 2$ (and we can check that $\sum_{k=0}^{5} a_k=0$), we can start from $i=5$ so that the partial sums $2, 2-1, 2-1+0, 2-1+0+5, 2-1+0+5+3, 2-1+0+5+3-9$ are all nonnegative.

If we can prove that such index $i$ always exists, what's an efficient algorithm to find the index $i$? There's an obvious $O(N^2)$ algorithm, but can we do it in $O(N)$? Thanks.

Note: this problem is somewhat similar to another problem: given an array of integers $a_0,a_1,a_2,...,a_n$ (they don't have to add up to 0), find $\max_{0\le i\le j\le n}\sum_{k=i}^j a_k$. This can be solved in time $O(n)$ as follows:

int maxsum = INT_MIN;

int sum = 0;

for (int i=0; i < a.length(); ++i){

if (sum <= 0) {sum = a[i]; }

else {sum += a[i];}

maxsum = max(sum, maxsum);

}

But in my original question, we are allowed to loop around, and we're required to find the index. So there are at least two differences between the two problems.

share|improve this question
add comment

2 Answers

Let $b_0=a_0+1$ and $b_k=a_k$ for $1\le k\le N-1$; $\langle b_0,\ldots,b_{N-1}\rangle$ is an integer sequence whose sum is $1$. Raney’s lemma says that there is an index $k$ such that every partial sum of the shifted sequence $\langle b_k,b_{k+1},\ldots,b_{k+N-1}\rangle$ is positive, where the indices are computed mod $N$. Since these are integer sequences, it follows that every partial sum of $\langle a_k,a_{k+1},\ldots,a_{k+N-1}\rangle$ is non-negative, the indices again being computed mod $N$. The link includes a proof of Raney’s lemma, which is given in more detail on page $360$ of Graham, Knuth, & Patashnik, Concrete Mathematics, second edition, together with a generalization of the lemma.

If you examine the proof closely, you’ll find that you can compute $k$ in the following way. If $s_j$ is the $j$-th partial sum of the original sequence, let $t_j=s_j-\frac{j}N$; then the desired index $k$ is the one that minimizes $t_k$. For example, for your sequence $\langle -1,0,5,3,-9,2\rangle$ we have

$$\langle t_0,t_1,t_2,t_3,t_4,t_5\rangle=\left\langle-1,-\frac76,\frac{22}6,\frac{39}6,-\frac{16}6,-\frac56\right\rangle\;,$$

with minimum element $t_5$. This computation is $O(N)$.

share|improve this answer
add comment

Thank you, Brian. Actually I came up with my own algorithm for this problem (also $O(N)$): call the array a[]

The logic is as follows: Keep in mind that the sum of the entries is 0. Starting from index i=0, and compute the partial sums a[i], a[i]+a[i+1], ..., Once a[i] + ... + a[j] becomes negative (where $j\ge i$), restart from i = j+1, and repeat again. But once the number of summand in the partial sum is equal to the length of the array, we are done (return i).

This works because if a[i], a[i]+a[i+1], ..., a[i]+...+a[j-1] are nonnegative, but a[i]+...+a[j] is negative, we know the answer cannot be any of i, i+1, ..., j. So we restart from i = j+1.

int i=0; while (true){

int sum = 0; int j = i; count = 0;

while (sum >= 0 && count < a.size()){

sum += a[ j% a.size() ];

++j; ++ count;

}

if (count == a.size()) {return i;}

i = j;

}

share|improve this answer
add comment

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.