Minimum Split Difference
easyArrays & Prefix Sums+10 XPTime limit 2s
Cut the array into two non-empty parts: a left part a[1..k] and a right part a[k+1..n]. Choose the cut so that the absolute difference between the sums of the two parts is as small as possible, and print that difference.
Input:
- line 1:
n - line 2:
nintegers
Output: the smallest possible |sum(left) − sum(right)|.
Constraints: 2 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹ (use 64-bit integers).
Think about it: compute the total once. Walk the cut from left to right keeping the left sum; the right sum is total − left, so each cut is checked in O(1).
Sample input 1
5 3 1 2 4 3
Sample output 1
1
Sample input 2
2 10 -10
Sample output 2
20
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).