# Minimize the sum of product of two arrays with permutations allowed

Given two arrays, A and B, of equal size n, the task is to find the minimum value of A * B + A * B +…+ A[n-1] * B[n-1]. Shuffling of elements of arrays A and B is allowed.

Examples :

```Input : A[] = {3, 1, 1} and B[] = {6, 5, 4}.
Output : 23
Minimum value of S = 1*6 + 1*5 + 3*4 = 23.

Input : A[] = { 6, 1, 9, 5, 4 } and B[] = { 3, 4, 8, 2, 4 }
Output : 80.
Minimum value of S = 1*8 + 4*4 + 5*4 + 6*3 + 9*2 = 80.
```

The idea is to multiply minimum element of one array to maximum element of another array. Algorithm to solve this problem:

1. Sort both the arrays A and B.
2. Traverse the array and for each element, multiply A[i] and B[n – i – 1] and add to the total.

Below is the implementation of this approach:

## C/C++

 `// C++ program to calculate minimum sum of product ` `// of two arrays. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns minimum sum of product of two arrays ` `// with permutations allowed ` `int` `minValue(``int` `A[], ``int` `B[], ``int` `n) ` `{ ` `    ``// Sort A and B so that minimum and maximum ` `    ``// value can easily be fetched. ` `    ``sort(A, A + n); ` `    ``sort(B, B + n); ` ` `  `    ``// Multiplying minimum value of A and maximum ` `    ``// value of B ` `    ``int` `result = 0; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``result += (A[i] * B[n - i - 1]); ` ` `  `    ``return` `result; ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `A[] = { 3, 1, 1 }; ` `    ``int` `B[] = { 6, 5, 4 }; ` `    ``int` `n = ``sizeof``(A) / ``sizeof``(A); ` `    ``cout << minValue(A, B, n) << endl; ` `    ``return` `0; ` `} `

/div>

## Java

 `// java program to calculate minimum ` `// sum of product of two arrays. ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// Returns minimum sum of product of two arrays ` `    ``// with permutations allowed ` `    ``static` `int` `minValue(``int` `A[], ``int` `B[], ``int` `n) ` `    ``{ ` `        ``// Sort A and B so that minimum and maximum ` `        ``// value can easily be fetched. ` `        ``Arrays.sort(A); ` `        ``Arrays.sort(B); ` ` `  `        ``// Multiplying minimum value of A ` `        ``// and maximum value of B ` `        ``int` `result = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``result += (A[i] * B[n - i - ``1``]); ` ` `  `        ``return` `result; ` `    ``} ` ` `  `    ``// Driven Program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `A[] = { ``3``, ``1``, ``1` `}; ` `        ``int` `B[] = { ``6``, ``5``, ``4` `}; ` `        ``int` `n = A.length; ` `        ``; ` `        ``System.out.println(minValue(A, B, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

## Python

 `# Python program to calculate minimum sum of product ` `# of two arrays. ` ` `  `# Returns minimum sum of product of two arrays ` `# with permutations allowed ` `def` `minValue(A, B, n): ` `    ``# Sort A and B so that minimum and maximum ` `    ``# value can easily be fetched. ` `    ``sorted``(A) ` `    ``sorted``(B) ` `  `  `    ``# Multiplying minimum value of A and maximum ` `    ``# value of B ` `    ``result ``=` `0` `    ``for` `i ``in` `range``(n): ` `        ``result ``+``=` `(A[i] ``*` `B[n ``-` `i ``-` `1``]) ` `  `  `    ``return` `result ` `  `  `# Driven Program ` `A ``=` `[``3``, ``1``, ``1``] ` `B ``=` `[``6``, ``5``, ``4``] ` `n ``=` `len``(A) ` `print` `minValue(A, B, n) ` ` `  `# Contributed by: Afzal Ansari `

## C#

 `// C# program to calculate minimum ` `// sum of product of two arrays. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Returns minimum sum of product  ` `    ``// of two arrays with permutations ` `    ``// allowed ` `    ``static` `int` `minValue(``int``[] a, ``int``[] b, ` `                                   ``int` `n) ` `    ``{ ` `         `  `        ``// Sort A and B so that minimum  ` `        ``// and maximum value can easily ` `        ``// be fetched. ` `        ``Array.Sort(a); ` `        ``Array.Sort(b); ` ` `  `        ``// Multiplying minimum value of  ` `        ``// A and maximum value of B ` `        ``int` `result = 0; ` `         `  `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``result += (a[i] * b[n - i - 1]); ` ` `  `        ``return` `result; ` `    ``} ` ` `  `    ``// Driven Program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `         `  `        ``int``[] a = { 3, 1, 1 }; ` `        ``int``[] b = { 6, 5, 4 }; ` `        ``int` `n = a.Length; ` `         `  `        ``Console.Write(minValue(a, b, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output :

```23
```

Time Complexity : O(n log n).

## tags:

Arrays Greedy Sorting Arrays Greedy Sorting