CODEWITHSUNDEEP
arraysalgorithm
Tanmoy Krishna Das
Tanmoy Krishna Das

Reputation: 670

How to swap members of two arrays so that the difference of sum of the elements of both arrays be minimum?

Given two unordered arrays array1 and array2, both of length LEN. for any i (0<=i<LEN), I can swap the values of array1[i] and array2[i]. Now, I have to swap them in a way so that the difference between sum of elements of array1 and array2 be minimum.

For Example:

array1=[1, 3, 5]
array2=[2, 4, 9]

Now, if I swap third member of both arrays (5 and 9), the difference becomes (1+3+9)-(2+4+5)=2.

I have found a solution using recursion. In my solution, I check all the valid combinations and where the difference is minimum, that is my answer. But here the runtime complexity is O(2^LEN). How can I do it more efficiently?

P.S. Array index starts at 0.

Upvotes: 1

Views: 1967

Answers (1)

borrible
borrible

Reputation: 17356

Consider a third array where the ith entry is the absolute difference of the ith values in array1 and array2. Assigning signs to these differences in the new array is equivalent to deciding whether or not you are swapping the values in your original arrays. You are now trying to solve the problem of minimising the sum of the (potentially sign swapped) values in the third array. This is the optimisation version of the Partition Problem.

Upvotes: 3

Related Questions