I have an array with N elements (N is even): [2, 4, 8, ..., 2^N]. I need to split it to 2 arrays, each with N/2 elements and get minimal absolute values of difference between sums of this arrays.
For 2, 4, 8, 16 answer is (2+16)-(4+8)=6. Can anyone explain to me the math side of solving this problem (no brute force)? Would the solution be the same if the original array is range[1, N]?
It looks fairly trivial since 2^N > sum(2..2^(N-1). Hence, to minimize the difference, you want to put 2^(N/2)+..._2^(N-1) in a different set than 2^N.
Would the solution be the same if the original array is range[1, N]?
In the case of the array 1, 2, ... N the answer is 0 or 1 depending on N mod 4.
If N = 4k then the minimum difference is 0 and is attained (for example) by the partition:
1 3 5 ... (2k - 1) (2k + 2) (2k + 4) ... 4k
2 4 6 ... 2k (2k + 1) (2k + 3) (2k + 5) ... (4k - 1)
If N = 4k + 2 then the minimum difference is 1 and is attained (for example) by the partition:
1 3 5 ... (2k + 1) (2k + 4) (2k + 6) ... (4k + 2)
2 4 6 ... (2k + 2) (2k + 3) (2k + 5) ... (4k + 1)
The general case of an arbitrary array is known as the partition problem with constraint of equal size, proved to be weakly NP-complete.