Any C/C++ Programmers?

[HawayiJahz]

Hello,

I've recently come across this problem in a programming challenge and in spite of my repeated attempts, I've not succeeded in solving the problem because I just can't figure out the algorithm. I was skeptical about posting this here but then I saw this, and I figure I could use some help.

There are some integers in an array of even size. Write a C program to rearrange the array elements such that the absolute difference between the summations of the left-half and right-half becomes minimum. Print the minimum absolute difference.

Please lay down the mathematical logic as to how the sorting ought to be performed in order that that the summations have minimum difference. This is the part I have trouble figuring out.

Any help is much appreciated.

[Altus_Demens]

I have not found any other universal solution but a "bruteforce".

Let's say that you have an array of N elements. The sum of all elements of the array is S1. You have to find a combination of any N/2 elements of the array with the sum S2 so that |S1/2 - S2| is as close to zero as possible. In order to achieve it, you have to iterate over all possible combinations of N/2 elements from N. On each iteration you should find the value of |S1/2 - S2| and if it is smaller than the previous value, you should store it, and you also should store the current set of the indices of the current elements (an additional array of N/2 elements would do this job). Thus, you'll have the minimal difference value and the indices of the items which would give this minimal difference, after the loop ends.

The complexity of this algorithm is o(C(n, n/2)) = o(n!/((n/2)!)^2). This means that the program would have to perform at least 10^29 operations to compute it for an array of 100 elements, so this algorithm is impractical.

I had a couple of ideas to achieve o(n^3) or even o(n^2), but I managed to find counter-examples for all of them. Try asking in the algorithmic programming communities, there must be a more neat solution.

If you have any questions, feel free to ask. I can also post my code sketch should you wish so.