742. Where the Left Side Wins
For each index i, compare the total of a[0] through a[i] against the total of a[i+1]
through a[n-1]. Count the indices where the LEFT total is at least the right total.
The index itself belongs to the left side. Values may be negative.
2 3 1 0 -> 3
1 2 3 -> 2
-1 1 -> 1
1 -1 1 -1 -> 4
## One total, one running left
There is no need to add up the right side at every index. Take the whole total once, then carry the left total as the scan advances:
right = total - left
so the test is left >= total - left, and left grows by a[i] before the next step.
Recomputing the right side inside the loop gives the same answers in O(n^2). This problem is
only about noticing the second pass is unnecessary.
## Add first, then test
The index belongs to the LEFT side, so a[i] must be added to left BEFORE the comparison.
That is the opposite order from problem 728, where the index belongs to neither side and the test comes first. Two problems, one line apart, and the difference is stated in the question rather than the code.
## Why the answer is not always a suffix of the indices
With non negative values the left total only grows and the right only shrinks, so once the left wins it keeps winning and the answer is a run of indices at the end.
With negatives that is false: the left total can rise above the right and fall back. On
1 -1 1 -1 every index qualifies, and on other inputs the qualifying indices are scattered.
Assuming the property is monotone, and stopping at the first success, is the mistake.
## The last index is not automatic
At i = n-1 the right side is empty and totals 0, so that index qualifies exactly when the
WHOLE total is at least 0. On an all-negative array it fails.
On -5 -5 -5 only index 0 qualifies, with a left total of -5 against a right total of
-10. Index 2 has a left total of -15 against 0 and fails. The answer is 1, not 3, and
assuming the last index always counts is the way to get 2 or 3 here.
On -1 1: index 0 has left -1 against right 1 and fails; index 1 has left 0
against right 0 and passes. The answer is 1.
## Overflow
100000 values of magnitude 10^9 total 10^14.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 100000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers, which may be negative.
Output
Print one integer, how many indices have a left total at least the right total.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.