Find Minimum sum of product of two arrays

Reading time: 20 minutes | Coding time: 5 minutes

Given two arrays array_One[] and array_Two[] of same size N. We need to first rearrange the arrays such that the sum of the product of pairs( 1 element from each) is minimum. That is SUM (A[i] * B[i]) for all i is minimum.

This can be solved using a greedy approach in O(N log N) time complexity. The basic idea is to sort one array in ascending order and the other array in descending order and find the sum in order wise products.

Example

Consider the following two arrays:

array_one[] = {7,5,1,4};
array_two[] = {6,17,9,3};

If we arrange the array_one like {1,4,5,7} and array_two like {17,9,6,3}

Then the sum of products is: (17 * 1) + (9 * 4) + (6 * 5) + (7 * 3) = 17 + 36 + 30 + 21 = 104 which is the minimun sum of products.

The minimum sum of product is 104

Algorithm

We will explore two approaches:

• A brute force approach O((N!)^2)
• A greedy approach O(N log N)

Naive approch

Brute force, calculate all the possible combination of pairs and thier sum, and keep a choose the minmum sum among them, this will have O((N!)^2) time complexity.

A set of N numbers has N! combinations. Considering there are 2 such sets and we need to pair them up, we have N! * N! combinations.

For each combination, we will compute the sum of products and store the minimum sum so far.

Pseudocode:

int find_minimum_sum(int array_1[], int array_2[])
{
    do
    {
        per_array_1 = generate_permutation(array_1);
        per_array_2 = generate_permutation(array_2);
        int sum = calcuate_sum(per_array_1, per_array_2);
        if(sum < min_sum)
            min_sum = sum;
    } while(more permutation pairs exist)
}

Greedy Approch O(N log N)

To minimize the sum of the product, we need to multiple a bigger number to a smaller number.Suppose we have A = {1,2,3} and B = {4,5,6}, so here we want to multiply 6 with a smallest number which is 1 in this case.

So to implement above approach we need to sort the array, one in ascending and other in descending order, so this will allow us to multiply the smallest number of one array to the largest number of other arrays.

STEP:

1. Sort both the array one in ascending and other in descending.
2. Multiply each pair from both arrays (Ai * Bi) for i ranging from 0 to N
3. Print the sum.
4. End.

Code

#include <bits/stdc++.h> 
using namespace std; 

int MSOP (vector<int> one, vector<int> two,int n) 
{ 
    sort(one.begin(),one.end());
    sort(two.begin(),two.end(),greater<int>());
    int sum  = 0; 
    for(int i=0;i<n;i++)
    {
        sum += one[i]*two[i];
    }
    return sum;
} 

int main() 
{ 
    vector <int>  one{14, 27, 33, 45}; 
    vector <int>  two{5,80,60,24};
    int n = one.size();    
    cout << "The minium sum of product of two arrays is: ";
    cout << MSOP(one,two,n); 
    return 0; 
}

Output

The minimum sum of the product of two arrays is: 3757

Complexity

• Worst case time complexity:Θ(nlogn)
• Space complexity: Θ(1)

Question