CODEWITHSUNDEEP
arraysalgorithm
kntgu
kntgu

Reputation: 184

Minimum sum of two arrays choosing half of the elements in each

Hello I am not a so called professional programmer. I have two arrays a1 and a2 of integers with same even length n. I need to find the minimum total sum of elements in a1 and a2 by selecting one element for each index and half of the selected elements should reside in a1 and the rest is in a2.

Example:

 a1 = [36, 72];  
 a2 = [35, 61];

The result should be 97 since we should choose 36 from a1 and 61 from a2. I think one solution would be choosing all possible n/2 elements in a1 and a2 and computing their results. Can a more efficient solution be found ?

Upvotes: 1

Views: 1076

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186678

Let's represent arrays a1 and a2 

    a1 = [36, 72];  
    a2 = [35, 61];

in a different way: we combine i-th indexes and compute a penalty = a2[i] - a1[i]:

    a = [(36, 35; penalty = -1), (72, 61; penalty = -11)]

Here penalty is a price we have to pay when we choose a2 value instead of a1. Let's sort by penalty

    a = [(72, 61; penalty = -11), (36, 35; penalty = -1)]

Now let's choose n/2 items with the lowest penalties and take a2 items; choose n/2 items with highest penalties and take a1 items:

    a = [(72, 61; penalty = -11), (36, 35; penalty = -1)]
         (72, 61; penalty = -11) - lowest,  take a2 item - 61
         (36, 35; penalty = -1)  - highest, take a1 item - 36

Time complexity is O(n * log(n)) - sorting.

C# implementation: 

  using System.Linq;

  ...

  int[] a1 = new int[] { 36, 72 };
  int[] a2 = new int[] { 35, 61 };

  var result = Enumerable
    .Range(0, a1.Length)
    .Select(i => new {
      v1 = a1[i],
      v2 = a2[i],
    })
    .OrderByDescending(item => item.v1 - item.v2)
    .Select((item, index) => index >= a1.Length / 2 
       ? item.v1 
       : item.v2)
    .Sum();

  Console.WriteLine(result);

Outcome:

  97

Upvotes: 2

SaiBot
SaiBot

Reputation: 3745

Choosing all possible n/2 elements and looking for the minimum will work, but will be very costly. In particular the runtime complexity will be O(n^n).

The basic idea is that you want to choose elements at index i with a high difference |a1[i] - a2[i]|. So here is a sketch of an algorithm:

  1. Build a new array d where d[i] = |a1[i] - a2[i]|
  2. Now take index i in descending order of d. So the index of the largest element in d first then the index of the second largest element in d and so on.
  3. For each index i you get from step 2. take the smaller element of a1[i] and a2[i] and add it to your sum. You also will track how many elements you took from a1 and how many from a2. If at one point you took n/2 of either you fill up the sum with the remaining entries form the other array.

Example:

a1 = [11, 12, 13, 12]

a2 = [15, 2,  30, 14]

d  = [4 , 10, 17, 2]

So here first pick a1[2] (13) since d[2] is the largest element in d and a1[2] < a2[2]. Next you pick a2[1] (2) since d[1] is the second largest element in d. Next you pick a1[0] (11) because of the same reasoning as before. Lastly, you realized that you already picked two elements from a1 thats why you add all remaining elements from a2 to your sum (14). The result is thus 13 + 2 + 11 + 14 = 40

When implemented efficiently this can run in O(n log n)

Upvotes: 1

Related Questions