CODEWITHSUNDEEP
algorithmsorting
Xon
Xon

Reputation: 69

How do I pick elements from two arrays such that the sum is minimum?

I have two arrays of equal length, and I can choose from either array1 or array2, and the output of the sum must be the smallest. However, the number of times I picked the element from array1 must be the same as I picked from array2.

Example:

array1 = [2, 3, 5, 1]

array2 = [1, 2, 3, 2]

The output will be 8, because:

At index0: I picked 2 from array1.
At index1: I picked 2 from array2.
At index2: I picked 3 from array2.
At index3: I picked 1 from array1.

My current approach: I sort the pair of array based on the element on array1. So I picked array1 at index0 and index1, then array2 at index2 and index3.

Example after sorted:

array1 = [1, 2, 3, 5]

array2 = [2, 1, 2, 3]

At index0: I picked 1 from array1.
At index1: I picked 2 from array1.
At index2: I picked 2 from array2.
At index3: I picked 3 from array2.

However, I may face a problem when the array is like this:

array1 = [2, 3, 5, 1]

array2 = [1, 7, 6, 2]

After sorted based on array1:

array1 = [1, 2, 3, 5]

array2 = [2, 1, 7, 6]

At index0: I picked 1 from array1.
At index1: I picked 2 from array1.
At index2: I picked 7 from array2.
At index3: I picked 6 from array2.

When the ideal solution is:

At index0: I picked 2 from array2.
At index1: I picked 1 from array2.
At index2: I picked 3 from array1.
At index3: I picked 5 from array1.

Can someone help me out with this? Thank you.

Upvotes: 1

Views: 750

Answers (1)

Jarod42
Jarod42

Reputation: 217255

Compute difference array1 - array2:

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

diff   = [1, 1 ,2, -1]
index  = [0, 1, 2, 3]

Sort it (and remember indexes):

sorted_diff: [-1, 1, 1, 2]
index2     : [ 3, 0, 1, 2]
            array1 | array2

You have to negate half the array to obtain minimum sum., so index1, index2 are from array2.

Example2:

array1 = [2, 3, 5, 1]
array2 = [1, 7, 6, 2]

diff   = [1, -4 ,-1, -1]
index  = [0, 1, 2, 3]

sorted = [-4, -1, -1, 1]
index2 = [ 1, 2, 3, 0]
        array1 | array2

So take from array2 index3, index0.

Upvotes: 2

Related Questions