740. Three Pieces That Weigh the Same
Can the array be cut into THREE non empty contiguous pieces with equal totals? Print yes or
no. Values may be negative.
0 2 1 -6 6 -7 9 1 2 0 1 -> yes
0 2 1 -6 6 7 9 -1 2 0 1 -> no
3 3 3 3 -> no
1 -1 1 -1 1 -1 -> yes
## Two cut points found greedily
If the whole total is not divisible by 3 the answer is no immediately.
Otherwise each piece must total T = total / 3. Sweep left to right with a running sum,
resetting it each time it reaches T:
run = 0; found = 0
for i in 0 .. n-2:
run += a[i]
if found == 0 and run == T: found = 1; run = 0
elif found == 1 and run == T: return yes
return no
## Why taking the FIRST place the prefix reaches T is safe
Suppose a valid split exists with its first cut at some position c, and let e be the
EARLIEST position where the running sum reaches T. Then e <= c, and the stretch between
them sums to T - T = 0.
Pulling the cut back from c to e moves that zero-summing stretch OUT of the first piece and
INTO the second. The first piece still totals T because it lost only zero, and the second
piece still totals T because it gained only zero. The second cut is untouched and the split
stays valid, so the earliest position never loses a solution.
That exchange argument is what turns a search over pairs of cut points into a single pass. With
negative values allowed, the running sum can reach T, leave it, and return, so "earliest" is
a genuine choice rather than the only one.
## The loop must stop before the last position
The third piece has to be non empty, so the second cut cannot fall at the very end. Running the
loop to n-1 accepts a split whose third piece is empty.
1 -1 0 is the case. Its total is 0 so T is 0. The first cut lands after position 1, and
an unguarded loop then finds the running sum back at 0 having consumed the ENTIRE array, so it
answers yes with an empty third piece. The correct answer is no.
The slip only shows when T is 0, because that is the only way the sum after the first cut can
reach T again at the very last position.
## Why T = 0 is not a special case here
With T = 0 the sweep still works: it looks for two positions where the running sum returns to
0, and the guard on the last position keeps the third piece non empty. 1 -1 1 -1 1 -1
answers yes through exactly that path.
## Relationship with problem 739
739 counts HOW MANY ways three pieces can share the ones equally, and gets a product of two gaps. This asks only WHETHER three pieces can share the total equally, and a single greedy pass settles it.
Counting needs every valid cut; deciding needs only one. That difference is why one problem is a product formula and the other is a scan.
## Overflow
200000 values of magnitude 10^9 total 2 * 10^14.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `-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 word on one line: yes if such a split exists, otherwise no.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.