347. 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 such a way that the absolute difference between the sums of the two halves is minimized.
In other words, if the sums of the two halves after partitioning are Sum1 and Sum2 respectively, you need to find the minimum value of abs(Sum1 - Sum2).
In other words, if the sums of the two halves after partitioning are Sum1 and Sum2 respectively, you need to find the minimum value of abs(Sum1 - Sum2).
Input Format
The first line contains an even integer n, representing the size of the array. The second line contains n space-separated integers, which are 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