Minimum sum of product of elements of pairs of the given array
Given an array arr[] of even number of element N in it. The task is to form N/2 pairs such that sum of product of elements in those pairs is minimum.
Examples
Input: arr[] = { 1, 6, 3, 1, 7, 8 }
Output: 270
Explanation:
The pair formed are {1, 1}, {3, 6}, {7, 8}
Product of sum of these pairs = 2 * 9 * 15 = 270
Input: arr[] = {2, 3, 90, 12}
Output: 510
Explanation:
Pairs should be created in this way {2, 3}, {12, 90}
Product of sum of these pairs = 5*112 = 510
Approach:
- Sort the elements in the given array arr[].
- Make pairs of first two-element, then next two-element and so on.
- Calculate the sum of product of corresponding pairs formed.
Below is the implementation of the above approach:
CPP
// C++ program to find the minimum // product of sum of pair of element // in array arr[] #include "bits/stdc++.h" using namespace std; // Function to find the minimum // product int minimumProduct( int * arr, int n) { // Sort the array using STL // sort() function sort(arr, arr + n); // Initialise product to 1 int product = 1; for ( int i = 0; i < n; i += 2) { // Find product of sum of // all pairs product *= (arr[i] + arr[i + 1]); } // Return the product return product; } // Driver code int main() { int arr[] = { 1, 6, 3, 1, 7, 8 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call to find product cout << minimumProduct(arr, n) << endl; return 0; } |
Java
// Java program to find the minimum // product of sum of pair of element // in array arr[] import java.util.*; class GFG{ // Function to find the minimum // product static int minimumProduct( int [] arr, int n) { // Sort the array using STL // sort() function Arrays.sort(arr); // Initialise product to 1 int product = 1 ; for ( int i = 0 ; i < n; i += 2 ) { // Find product of sum of // all pairs product *= (arr[i] + arr[i + 1 ]); } // Return the product return product; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 6 , 3 , 1 , 7 , 8 }; int n = arr.length; // Function call to find product System.out.print(minimumProduct(arr, n) + "\n" ); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 program to find the minimum # product of sum of pair of element # in array arr[] # Function to find the minimum # product def minimumProduct(arr, n): # Sort the array using STL # sort() function arr = sorted (arr) # Initialise product to 1 product = 1 for i in range ( 0 , n, 2 ): # Find product of sum of # all pairs product * = (arr[i] + arr[i + 1 ]) # Return the product return product # Driver code arr = [ 1 , 6 , 3 , 1 , 7 , 8 ] n = len (arr) # Function call to find product print (minimumProduct(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the minimum // product of sum of pair of element // in array arr[] using System; class GFG { // Function to find the minimum // product static int minimumProduct( int [] arr, int n) { // Sort the array // sort() function Array.Sort(arr); // Initialise product to 1 int product = 1; for ( int i = 0; i < n; i += 2) { // Find product of sum of // all pairs product *= (arr[i] + arr[i + 1]); } // Return the product return product; } // Driver code static void Main() { int [] arr = new int [] { 1, 6, 3, 1, 7, 8 }; int n = arr.Length; // Function call to find product Console.Write(minimumProduct(arr, n)); } } // This code is contributed by shubhamsingh10 |
Javascript
<script> // Javascript program to find the minimum // product of sum of pair of element // in array arr[] // Function to find the minimum // product function minimumProduct(arr, n) { // Sort the array using STL // sort() function arr.sort(); // Initialise product to 1 let product = 1; for (let i = 0; i < n; i += 2) { // Find product of sum of // all pairs product *= (arr[i] + arr[i + 1]); } // Return the product return product; } // Driver code let arr = [ 1, 6, 3, 1, 7, 8 ]; let n = arr.length; // Function call to find product document.write(minimumProduct(arr, n) + "<br>" ); // This code is contributed by Mayank Tyagi </script> |
270
Time Complexity: O(N*log N) the inbuilt sort function takes N log N time to complete all operations, hence the overall time taken by the algorithm is N log N
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant