740. Minimize Sum Difference by Partitioning into Two Equal Halves
0
Hard
Given an array of integers with an even size, you need to divide the array into two equal halves in a way that minimizes the absolute difference between the sums of the two halves.
In other words, let's denote the sums of the two halves after partitioning as Sum1 and Sum2 respectively. Your task is to find the minimum value of abs(Sum1 - Sum2).
In other words, let's denote the sums of the two halves after partitioning as Sum1 and Sum2 respectively. Your task is to find the minimum value of abs(Sum1 - Sum2).
Input Format
The first line contains a single even integer n. The second line contains n space-separated integers representing the elements of the array.
Output Format
Print the minimum possible absolute difference.
Example
Input
4
3 7 9 3
Output
2
Constraints
1<=n<=30
Elements of the array are within the range of -10^6 to 10^6
Elements of the array are within the range of -10^6 to 10^6
Loading...
View Submissions
Console