Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.