An algorithm to find the maximum sum of products of two arrays.
We will implement a simple algorithm in javascript to find the maximum sum of products of given two arrays. Both the arrays will be of the same length.
Example
Input: [1, 2, 3] [5, 4, 3] [4, 7, 5, 2] [2, 3, 2 ,1] Output: 26 = 5 * 3 + 4 * 2 + 3 * 1 41 = 7 * 3 + 5 * 2 + 4 * 2 + 2 * 1
Implementation
- We will first sort both the arrays in any order.
- Then we will find the product of the each elements and add them.
- Everything will be written in ES6.
let productSum = (arr1, arr2) => {
//sort the arrays in ascending order
arr1.sort();
arr2.sort();
let sum = 0;
//calculate the sum of the products
for(let i = 0; i < arr1.length; i++){
sum += arr1[i] * arr2[i];
}
return sum;
}
Input: console.log(productSum([1, 2, 3], [5, 4, 3])); console.log(productSum([4, 7, 5, 2], [2, 3, 2 ,1])); Output: 26 41
Time complexity: O(nlogn);
Space complexity: O(1);
Time and Space complexity
- We are sorting both the arrays which will take O(nlogn) then we are calculating the sum of the products of each element which will take O(n), so Time complexity is O(nlogn).
- We are using constant space, so Space complexity is O(n).
Vivek says:
Hey can you add some react machine coding questions which gets asked at start-ups.
Prashant Yadav says:
Sure
Kevin says:
What is the maximum part?
Why sort?
Prashant Yadav says:
We sort the arrays so that we should be able to multiply bigger numbers together and then add them to get the maximum sum.