# Maximize 3rd element sum in quadruplet sets formed from given Array

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:10Explanation:

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 Y` `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]` ` ` `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 code` `int` `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 Array` `import` `java.util.*;` `class` `GFG{` `// Function to find the maximum` `// possible value of Y` `static` `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 code` `public` `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 Array` `using` `System;` `class` `GFG{` `// Function to find the maximum` `// possible value of Y` `static` `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 code` `public` `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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.