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// productint 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 codeint 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// productstatic 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 codepublic 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# productdef 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 codearr = [1, 6, 3, 1, 7, 8]n = len(arr)# Function call to find productprint(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// productfunction 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> |
Output:
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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
