Given an array arr containing N values describing the priority of N jobs. The task is to form sets of quadruplets (W, X, Y, Z) to be done each day such that W >= X >= Y >= Z and in doing so, maximize the sum of all Y across all quadruplet sets.
Note: N will always be a multiple of 4.
Examples:
Input: Arr[] = {2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2}
Output: 10
Explanation:
We can form 3 quadruplet sets as [7, 5, 5, 1], [4, 3, 3, 1], [2, 2, 2, 1].
The summation of all Y’s are 5 + 3 + 2 = 10 which is the maximum possible value.
Input: arr[] = {1, 51, 91, 1, 1, 16, 1, 51, 48, 16, 1, 49}
Output: 68
Approach: To solve the problem mentioned above we can observe that:
- Irrespective of Y, (W, X) >= Y, i.e., higher values of W and X are always lost and don’t contribute to the answer. Therefore, we must keep these values as low as possible but greater or equal to Y.
- Similarly, value for Z is always lost and must be less than Y. Therefore, it must be as low as possible.
Hence, to satisfy the above condition we have to:
- first sort given array in descending order.
- initialize a pointer that points to the third element of each pair from index 0.
- subtract count of such pairs from the size of array i.e, N.
Below is the implementation of the above approach:
C++
// C++ code to Maximize 3rd element// sum in quadruplet sets formed// from given Array#include <bits/stdc++.h>using namespace std;// Function to find the maximum// possible value of Yint formQuadruplets(int arr[], int n){ int ans = 0, pairs = 0; // pairs contain count // of minimum elements // that will be utilized // at place of Z. // it is equal to count of // possible pairs that // is size of array divided by 4 pairs = n / 4; // sorting the array in descending order // so as to bring values with minimal // difference closer to arr[i] sort(arr, arr + n, greater<int>()); for (int i = 0; i < n - pairs; i += 3) { // here, i+2 acts as a // pointer that points // to the third value of // every possible quadruplet ans += arr[i + 2]; } // returning the optimally // maximum possible value return ans;}// Driver codeint main(){ // array declaration int arr[] = { 2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2 }; // size of array int n = sizeof(arr) / sizeof(arr[0]); cout << formQuadruplets(arr, n) << endl; return 0;} |
Java
// Java code to Maximize 3rd element// sum in quadruplet sets formed// from given Arrayimport java.util.*;class GFG{// Function to find the maximum// possible value of Ystatic int formQuadruplets(Integer arr[], int n){ int ans = 0, pairs = 0; // pairs contain count // of minimum elements // that will be utilized // at place of Z. // it is equal to count of // possible pairs that // is size of array divided by 4 pairs = n / 4; // sorting the array in descending order // so as to bring values with minimal // difference closer to arr[i] Arrays.sort(arr, Collections.reverseOrder()); for (int i = 0; i < n - pairs; i += 3) { // here, i+2 acts as a // pointer that points // to the third value of // every possible quadruplet ans += arr[i + 2]; } // returning the optimally // maximum possible value return ans;}// Driver codepublic static void main(String[] args){ // array declaration Integer arr[] = { 2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2 }; // size of array int n = arr.length; System.out.print( formQuadruplets(arr, n) + "\n");}}// This code contributed by Rajput-Ji |
Python3
# Python3 code to maximize 3rd element # sum in quadruplet sets formed # from given Array # Function to find the maximum # possible value of Y def formQuadruplets(arr, n): ans = 0 pairs = 0 # Pairs contain count of minimum # elements that will be utilized # at place of Z. It is equal to # count of possible pairs that # is size of array divided by 4 pairs = n // 4 # Sorting the array in descending order # so as to bring values with minimal # difference closer to arr[i] arr.sort(reverse = True) for i in range(0, n - pairs, 3): # Here, i+2 acts as a pointer that # points to the third value of # every possible quadruplet ans += arr[i + 2] # Returning the optimally # maximum possible value return ans # Driver code # Array declaration arr = [ 2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2 ] # Size of array n = len(arr) print(formQuadruplets(arr, n)) # This code is contributed by divyamohan123 |
C#
// C# code to maximize 3rd element// sum in quadruplet sets formed// from given Arrayusing System;class GFG{// Function to find the maximum// possible value of Ystatic int formQuadruplets(int []arr, int n){ int ans = 0, pairs = 0; // Pairs contain count of minimum // elements that will be utilized at // place of Z. It is equal to count of // possible pairs that is size of // array divided by 4 pairs = n / 4; // Sorting the array in descending order // so as to bring values with minimal // difference closer to arr[i] Array.Sort(arr); Array.Reverse(arr); for(int i = 0; i < n - pairs; i += 3) { // Here, i+2 acts as a // pointer that points // to the third value of // every possible quadruplet ans += arr[i + 2]; } // Returning the optimally // maximum possible value return ans;}// Driver codepublic static void Main(String[] args){ // Array declaration int []arr = { 2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2 }; // Size of array int n = arr.Length; Console.Write(formQuadruplets(arr, n) + "\n");}}// This code is contributed by amal kumar choubey |
Javascript
<script> // JavaScript code to maximize 3rd element // sum in quadruplet sets formed // from given Array // Function to find the maximum // possible value of Y function formQuadruplets(arr, n) { var ans = 0, pairs = 0; // Pairs contain count of minimum // elements that will be utilized at // place of Z. It is equal to count of // possible pairs that is size of // array divided by 4 pairs = parseInt(n / 4); // Sorting the array in descending order // so as to bring values with minimal // difference closer to arr[i] arr.sort().reverse(); for (var i = 0; i < n - pairs; i += 3) { // Here, i+2 acts as a // pointer that points // to the third value of // every possible quadruplet ans += arr[i + 2]; } // Returning the optimally // maximum possible value return ans; } // Driver code // Array declaration var arr = [2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2]; // Size of array var n = arr.length; document.write(formQuadruplets(arr, n) + "<br>"); </script> |
Output:
10
Time Complexity: O(n*log(n))
Auxiliary Space: O(1)
Take a part in the ongoing discussion
