Dividing an integer array into two equal sized sub-arrays?

Question

I came across this question and couldn't find a reasonable solution. How would you divide an unsorted integer array into 2 equal sized sub-arrays such that, difference between sub-array sums is minimum.

For example: given an integer array a[N] (unsorted), we want to split the array into be split into a1 and a2 where a1.length == a2.length i.e N/2 and (sum of all numbers in a1 - sum of all numbers in a2) should be minimum.

For the sake of simplicity, let's assume all numbers are positve but there might be repetitions.

@SparKot okay, i'm not aware of that detail. Lets say unsorted. — rplusg
– rplusg, Commented Jan 29, 2013 at 17:31
Looks like you have pretty much the partition problem. Although not an exact dupe, it looks like the answers to a previous question probably apply here as well. — Jerry Coffin
– Jerry Coffin, Commented Jan 29, 2013 at 17:36
as @JerryCoffin said that it's partition problem with a simple modification. I can add that the modification would be on the matter of a1.length == a2.length and that can be solved with getting the minimum numbers from the largest array and putting them in the other one till having the condition satisfied. — mamdouh alramadan
– mamdouh alramadan, Commented Jan 29, 2013 at 19:04

Andrew Mao · Accepted Answer · 2013-01-29 19:53:50Z

3

While others have mentioned that this is a case of the partition problem with modification, I'd like to point out, more specifically, that it is actually a special case of the minimum makespan problem with two machines. Namely, if you solve the two-machine makespan problem and obtain a value m, you obtain the minimum difference 2*m - sum(i : i in arr)

As the wikipedia article states, the problem is NP-complete for more than 2 machines. However, in your case, the List scheduling algorithm, which in general provides an approximate answer, is optimal and polynomial-time for the two-machine and three-machine case given a sorted list in non-increasing order.

For details, and some more theoretical results on this algorithm, see here.

edited Jan 29, 2013 at 19:53

answered Jan 29, 2013 at 19:45

Andrew Mao

37k24 gold badges148 silver badges228 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dividing an integer array into two equal sized sub-arrays?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related