672. Merging Neighbours Until It Reads the Same Both Ways
One MERGE replaces two ADJACENT values by their sum, shortening the array by one. Print the fewest merges needed to make the array read the same forwards and backwards.
4 3 2 1 2 3 1 -> 2 merge 3 and 1 into 4, then 1 and 2 into 3, giving 4 3 2 3 4
1 2 3 4 -> 3
1 2 3 2 1 -> 0 already a palindrome
## Work inward from the ends
Compare the current front value with the current back value.
· equal: they are settled. Move both inward. · front smaller: it can never grow except by merging with its right neighbour, so merge, and charge one move. · back smaller: merge it with its left neighbour, and charge one move.
i = 0, j = n-1, x = a[i], y = a[j], moves = 0
while i < j:
x == y -> i += 1; j -= 1; refresh x and y
x < y -> i += 1; x += a[i]; moves += 1
x > y -> j -= 1; y += a[j]; moves += 1
## Why merging the smaller side is forced
Values are positive, so a merge only ever INCREASES a side's total. If the front is smaller than the back, no amount of merging on the back can bring it down to match, so the front must grow. There is no choice to make and therefore nothing to search.
That is what turns a problem that looks like a search into a linear sweep, and it depends entirely on the values being positive. With zeros or negatives allowed the argument collapses, which is why the constraints exclude them.
## Why the outer pair can be settled and forgotten
Once the two ends match they form the outermost pair of the palindrome, and nothing inside can change them: merges inside never touch values already outside the working range.
So the problem reduces to the same question on a shorter range, and the sweep never revisits.
## Reading the sample
4 3 2 1 2 3 1, step by step:
front 4, back 1 -> back is smaller: merge 3 and 1 into 4 1 merge
front 4, back 4 -> equal, both settle and move inward
front 3, back 2 -> back is smaller: merge 1 and 2 into 3 1 merge
front 3, back 3 -> equal, both settle; the pointers meet
The array has become 4 3 2 3 4, which reads the same both ways, in 2 merges.
## Overflow
Merging every value gives the whole sum, up to 200000 times 10^9, which is 2 * 10^14.
The running totals need 64 bits.
## Boundaries
An array of one value is already a palindrome. An array that is already a palindrome answers 0.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n positive integers.
Output
Print one integer, the fewest merges needed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.