The Perfect Split
Aarav is a student at UptoSkills Arena and is practicing for a competition. He has a list of n integers, a_1, a_2, ..., a_n. He wants to split this list into two contiguous sublists: a prefix and a suffix. For example, if the list is [1, 2, 3, 4, 5], a possible split could be [1, 2] (prefix) and [3, 4, 5] (suffix).
He defines the 'split value' as the absolute difference between the sum of elements in the prefix and the sum of elements in the suffix.
Aarav is looking for a split such that the split value is as small as possible. If there are multiple splits that achieve the minimum split value, he wants the one where the prefix is as long as possible.
Find the minimum possible split value and the length of the longest prefix that achieves this minimum split value.
Input
The first line contains a single integer n (2 <= n <= 200000). The second line contains n integers a_1, a_2, ..., a_n (-10^9 <= a_i <= 10^9).
Output
Print two integers: the minimum split value and the length of the longest prefix that achieves it.
Constraints
2 <= n <= 200000 -10^9 <= a_i <= 10^9
Example 1
5 1 2 3 4 5
3 3
Prefix [1, 2, 3] (sum 6), Suffix [4, 5] (sum 9). Diff = |6-9| = 3. Length of prefix is 3. This is the minimum difference. For prefix [1, 2, 3, 4] (sum 10), suffix [5] (sum 5). Diff = |10-5| = 5. For prefix [1, 2] (sum 3), suffix [3, 4, 5] (sum 12). Diff = |3-12| = 9. Minimum difference is 3, achieve
Example 2
4 -1 2 -3 4
0 2
Prefix [-1, 2] (sum 1), Suffix [-3, 4] (sum 1). Diff = |1-1| = 0. Length 2. Prefix [-1, 2, -3] (sum -2), Suffix [4] (sum 4). Diff = |-2-4| = 6. Length 3. Minimum difference 0, achieved with prefix length 2.
Hints
Similar problems
- Longest Subarray with Equal Number of Zeroes and OnesHard
- Subarray Sum and CountMedium
- Matrix Zero Sum SubgridsMedium
- Longest Subarray With Sum XMedium
- Longest Subarray with Sum at Most KMedium
- Count XOR PairsMedium
More topics: Hash Map and Hashing problems, Two Pointers problems, Prefix Sums problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 5
4 -1 2 -3 4