Minimum sum obtained by choosing N number from given N pairs
Given an array arr[] of N pairs of integers (A, B) where N is even, the task is to find the minimum sum of choosing N elements such that value A and B from all the pairs are chosen exactly (N/2) times.
Examples:
Input: N = 4, arr[][] = { {7, 20}, {300, 50}, {30, 200}, {30, 20} }
Output: 107
Explanation:
Choose value-A from 1st pair = 7.
Choose value-B from 2nd pair = 50.
Choose value-A from 3rd pair = 30.
Choose value-B from 4th pair = 20.
The minimum sum is 7 + 50 + 30 + 20 = 107.
Input: N = 4, arr[][] = { {10, 20}, {400, 50}, {30, 200}, {30, 20} }
Output: 110
Explanation:
Choose value-A from 1st pair = 10.
Choose value-B from 2nd pair = 50.
Choose value-A from 3rd pair = 30.
Choose value-B from 4th pair = 20.
The minimum sum is 10 + 50 + 30 + 20 = 110.
Approach: This problem can be solved using Greedy Approach. Below are the steps:
- For each pair (A, B) in the given array, store the value of (B – A) with the corresponding index in temporary array(say temp[]). The value (B – A) actually defines how much cost is minimized if A is chosen over B for each element.
- The objective is to minimize the total cost. Hence, sort the array temp[] in decreasing order.
- Pick the first N/2 elements from the array temp[] by choosing A as first N/2 elements will have the maximum sum when A is chosen over B.
- For remaining N/2 elements choose B as the sum of values can be minimized.
Below is the implementation of the above approach:
CPP
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to choose the elements A // and B such the sum of all elements // is minimum int minSum( int arr[][2], int n) { // Create an array of pair to // store Savings and index pair< int , int > temp[n]; // Traverse the given array of pairs for ( int i = 0; i < 2 * n; i++) { // Sum minimized when A // is chosen over B for // i-th element. temp[i].first = arr[i][1] - arr[i][0]; // Store index for the // future reference. temp[i].second = i; } // Sort savings array in // non-increasing order. sort(temp, temp + 2 * n, greater<pair< int , int > >()); // Storing result int res = 0; for ( int i = 0; i < 2 * n; i++) { // First n elements choose // A and rest choose B if (i < n) res += arr[temp[i].second][0]; else res += arr[temp[i].second][1]; } // Return the final Sum return res; } // Driver Code int main() { // Given array of pairs int arr[4][2] = { { 7, 20 }, { 300, 50 }, { 30, 200 }, { 30, 20 } }; // Function Call cout << minSum(arr, 2); } |
Java
/*package whatever //do not write package name here */ import java.util.*; public class GFG{ static class Pair<K,V>{ K first; V second; Pair(K k, V v){ first = k; second = v; } } // Function to choose the elements A // and B such the sum of all elements // is minimum static int minSum( int arr[][], int n) { // Create an array of pair to // store Savings and index Pair<Integer, Integer> temp[] = new Pair[ 2 *n]; // Traverse the given array of pairs for ( int i = 0 ; i < 2 * n; i++) { // Sum minimized when A // is chosen over B for // i-th element. temp[i] = new Pair(arr[i][ 1 ] - arr[i][ 0 ],i); // Store index for the // future reference. } // Sort savings array in // non-increasing order. Arrays.sort(temp,(a,b)->b.first-a.first); // Storing result int res = 0 ; for ( int i = 0 ; i < 2 * n; i++) { // First n elements choose // A and rest choose B if (i < n) res += arr[temp[i].second][ 0 ]; else res += arr[temp[i].second][ 1 ]; } // Return the final Sum return res; } public static void main(String[] args) { // Given array of pairs int arr[][] = { { 7 , 20 }, { 300 , 50 }, { 30 , 200 }, { 30 , 20 } }; // Function Call System.out.println(minSum(arr, 2 )); } } // This code is contributed by aadityaburujwale. |
Python3
# Python3 program for the above approach # Function to choose the elements A # and B such the sum of all elements # is minimum def minSum(arr, n): # Create an array of pair to # store Savings and index temp = [ None ] * ( 2 * n) # Traverse the given array of pairs for i in range ( 2 * n): # Sum minimized when A # is chosen over B for # i-th element. temp[i] = (arr[i][ 1 ] - arr[i][ 0 ], i) # Sort savings array in # non-increasing order. temp.sort(reverse = True ) # Storing result res = 0 for i in range ( 2 * n): # First n elements choose # A and rest choose B if (i < n): res + = arr[temp[i][ 1 ]][ 0 ] else : res + = arr[temp[i][ 1 ]][ 1 ] # Return the final Sum return res # Driver Code if __name__ = = '__main__' : # Given array of pairs arr = [[ 7 , 20 ], [ 300 , 50 ], [ 30 , 200 ], [ 30 , 20 ]] # Function Call print (minSum(arr, 2 )) |
C#
using System; using System.Linq; class GFG { // Function to choose the elements A // and B such the sum of all elements // is minimum public static int MinSum( int [,] arr, int n) { // Create an array of Tuple to store savings and index Tuple< int , int >[] temp = new Tuple< int , int >[2 * n]; // Traverse the given array of pairs for ( int i = 0; i < 2 * n; i++) { // Sum minimized when A is chosen over B for i-th element. temp[i] = new Tuple< int , int >(arr[i, 1] - arr[i, 0], i); } // Sort savings array in non-increasing order. Array.Sort(temp, (x, y) => y.Item1.CompareTo(x.Item1)); // Storing result int res = 0; for ( int i = 0; i < 2 * n; i++) { // First n elements choose A and rest choose B if (i < n) { res += arr[temp[i].Item2, 0]; } else { res += arr[temp[i].Item2, 1]; } } // Return the final Sum return res; } public static void Main( string [] args) { // Given array of pairs int [,] arr = { { 7, 20 }, { 300, 50 }, { 30, 200 }, { 30, 20 } }; Console.WriteLine(MinSum(arr, 2)); } } // This code is contributed by poojaagarwal2. |
Javascript
// Javascript program for the above approach // Function to choose the elements A // and B such the sum of all elements // is minimum function minSum(arr, n) { // Create an array of pair to // store Savings and index let temp = new Array(2 * n).fill( null ); // Traverse the given array of pairs for (let i = 0; i < 2 * n; i++) { // Sum minimized when A // is chosen over B for // i-th element. temp[i] = [arr[i][1] - arr[i][0], i] } // Sort savings array in // non-increasing order. temp.sort((a, b) => b[0] - a[0]); // Storing result let res = 0 for (let i = 0; i < 2 * n; i++) { // First n elements choose // A and rest choose B if (i < n) res += arr[temp[i][1]][0] else res += arr[temp[i][1]][1] } // Return the final Sum return res } // Driver Code // Given array of pairs let arr = [[7, 20], [300, 50], [30, 200], [30, 20]] // Function Call console.log(minSum(arr, 2)) // This code is contributed by saurabh_jaiswal. |
107
Time Complexity: O(N*log(N))
Auxiliary Space Complexity: O(N)
Contact Us