# Distribute given arrays into K sets such that total sum of maximum and minimum elements of all sets is maximum

Given two arrays, the first **arr[]** of size **N** and the second **brr[]** of size **K**. The task is to divide the first array **arr[] **into **K** sets such that the** i-th** set should contain **brr[i]** elements from the second array **brr[]**, and the total sum of maximum and minimum elements of all sets is maximum.

**Examples:**

Input:n = 4, k = 2, arr[] = {10, 10, 11, 11 }, brr[] = {2, 2 }Output:42Explanation:First set = 10 11, sum of maximum and minimum = 21, Second set = 10 11, sum of maximum and minimum = 21. Total sum = 42 (maximum possible)

Input:n = 4, k = 4, arr[] = {10, 10, 10, 10}, brr[] = {1, 1, 1, 1 }Output:42

**Approach: **Give the greatest elements to set with size =1. For the rest, sort both the arrays, **arr[] **in descending order and **brr[] **in ascending order. Now, if the size of the set is not 1, then add the minimum element to the answer. Follow the steps below to solve the problem:

- Sort the arrays,
**arr[]**in descending order and**brr[]**in ascending order. - Initialize the variable say
**ans**as**0**to store the value of the answer and**cnt**as**0**to count the number of sets with size 1. - Iterate in a range
**[0, K]**and count the number of sets at size 1 and store the value in the variable**cnt.** - Iterate in a range
**[0, K]**and perform the following steps.- Add the value of
**arr[i]**to the variable**ans**as the value**arr[i]**will be the maximum value for the**i-th**set. - If the value of
**cnt**is greater than 0, then, add the value**arr[i]**again as it will be minimum value also and subtract the value of**cnt**by 1.

- Add the value of
- Initialize the variable
**from**as**K**to maintain the counter. - Iterate in a range
**[0, K]**and perform the following steps.- If the value of
**brr[i]**is**1,**then, continue. - Add the value of
**arr[from + brr[i] – 2]**to the answer. - Increase the value of
**from**by**brr[i]-1.**

- If the value of
- Print the final value of answer.

Below is the implementation of the above approach.

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `typedef` `long` `long` `ll;` `// Function to find K sets such that the` `// sum of maximum and minimum of all sets` `// is maximum` `void` `findSets(` `int` `n, ` `int` `k, vector<` `int` `>& arr,` ` ` `vector<` `int` `>& brr)` `{` ` ` `ll ans = 0;` ` ` `// Sort both the arrays` ` ` `// arr[] in descending order.` ` ` `// brr[] in ascending order.` ` ` `sort(arr.begin(), arr.end());` ` ` `sort(brr.begin(), brr.end());` ` ` `reverse(arr.begin(), arr.end());` ` ` `int` `cnt = 0;` ` ` `// Count the number of sets with size 1` ` ` `for` `(` `int` `& v : brr) {` ` ` `if` `(v == 1)` ` ` `cnt++;` ` ` `}` ` ` `// Assign the first K maximum elements` ` ` `// to the sets and add them as minimum` ` ` `// also for sets with size 1.` ` ` `for` `(` `int` `i = 0; i < k; i++) {` ` ` `ans += arr[i];` ` ` `if` `(cnt > 0) {` ` ` `ans += arr[i];` ` ` `cnt--;` ` ` `}` ` ` `}` ` ` `int` `from = k;` ` ` `// Add the minimum element from the set.` ` ` `for` `(` `int` `i = 0; i < k; i++) {` ` ` `if` `(brr[i] == 1)` ` ` `continue` `;` ` ` `ans += arr[from + brr[i] - 2];` ` ` `from += brr[i] - 1;` ` ` `}` ` ` `cout << ans << ` `'\n'` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `n, k;` ` ` `n = 4;` ` ` `k = 2;` ` ` `vector<` `int` `> arr{ 10, 10, 11, 11 };` ` ` `vector<` `int` `> brr{ 2, 2 };` ` ` `findSets(n, k, arr, brr);` ` ` `return` `0;` `}` |

## Java

`import` `java.util.Arrays;` `import` `java.util.Collections;` `// C++ program for the above approach` `class` `GFG {` ` ` `// Function to find K sets such that the` ` ` `// sum of maximum and minimum of all sets` ` ` `// is maximum` ` ` `public` `static` `void` `findSets(` `int` `n, ` `int` `k, ` `int` `[] arr, ` `int` `[] brr) {` ` ` `int` `ans = ` `0` `;` ` ` `// Sort both the arrays` ` ` `// arr[] in descending order.` ` ` `// brr[] in ascending order.` ` ` `Arrays.sort(arr);` ` ` `Arrays.sort(brr);` ` ` `Collections.reverse(Arrays.asList(arr));` ` ` `int` `cnt = ` `0` `;` ` ` `// Count the number of sets with size 1` ` ` `for` `(` `int` `v : brr) {` ` ` `if` `(v == ` `1` `)` ` ` `cnt++;` ` ` `}` ` ` `// Assign the first K maximum elements` ` ` `// to the sets and add them as minimum` ` ` `// also for sets with size 1.` ` ` `for` `(` `int` `i = ` `0` `; i < k; i++) {` ` ` `ans += arr[i];` ` ` `if` `(cnt > ` `0` `) {` ` ` `ans += arr[i];` ` ` `cnt--;` ` ` `}` ` ` `}` ` ` `int` `from = k;` ` ` `// Add the minimum element from the set.` ` ` `for` `(` `int` `i = ` `0` `; i < k; i++) {` ` ` `if` `(brr[i] == ` `1` `)` ` ` `continue` `;` ` ` `ans += arr[from + brr[i] - ` `2` `];` ` ` `from += brr[i] - ` `1` `;` ` ` `}` ` ` `System.out.println(ans);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[]) {` ` ` `int` `n, k;` ` ` `n = ` `4` `;` ` ` `k = ` `2` `;` ` ` `int` `[] arr = { ` `10` `, ` `10` `, ` `11` `, ` `11` `};` ` ` `int` `[] brr = { ` `2` `, ` `2` `};` ` ` `findSets(n, k, arr, brr);` ` ` `}` `}` `// This code is contributed by gfgking.` |

## Python3

`# python 3 program for the above approach` `# Function to find K sets such that the` `# sum of maximum and minimum of all sets` `# is maximum` `def` `findSets(n, k, arr, brr):` ` ` `ans ` `=` `0` ` ` `# Sort both the arrays` ` ` `# arr[] in descending order.` ` ` `# brr[] in ascending order.` ` ` `arr.sort()` ` ` `brr.sort()` ` ` `arr ` `=` `arr[:` `-` `1` `]` ` ` `cnt ` `=` `0` ` ` `# Count the number of sets with size 1` ` ` `for` `v ` `in` `brr:` ` ` `if` `(v ` `=` `=` `1` `):` ` ` `cnt ` `+` `=` `1` ` ` `# Assign the first K maximum elements` ` ` `# to the sets and add them as minimum` ` ` `# also for sets with size 1.` ` ` `for` `i ` `in` `range` `(k):` ` ` `ans ` `+` `=` `arr[i]` ` ` `if` `(cnt > ` `0` `):` ` ` `ans ` `+` `=` `arr[i]` ` ` `cnt ` `-` `=` `1` ` ` `from1 ` `=` `k` ` ` `# Add the minimum element from the set.` ` ` `for` `i ` `in` `range` `(k):` ` ` `if` `(brr[i] ` `=` `=` `1` `):` ` ` `continue` ` ` `if` `from1 ` `+` `brr[i] ` `-` `2` `>` `len` `(arr)` `-` `1` `:` ` ` `continue` `;` ` ` `ans ` `+` `=` `arr[from1 ` `+` `brr[i] ` `-` `2` `]` ` ` `from1 ` `+` `=` `brr[i] ` `-` `1` ` ` `print` `(ans)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `n ` `=` `4` ` ` `k ` `=` `2` ` ` `arr ` `=` `[` `10` `, ` `10` `, ` `11` `, ` `11` `]` ` ` `brr ` `=` `[` `2` `, ` `2` `]` ` ` `findSets(n, k, arr, brr)` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to find K sets such that the` `// sum of maximum and minimum of all sets` `// is maximum` `static` `void` `findSets(` `int` `n, ` `int` `k, List<` `int` `> arr,` ` ` `List<` `int` `> brr)` `{` ` ` `int` `ans = 0;` ` ` `// Sort both the arrays` ` ` `// arr[] in descending order.` ` ` `// brr[] in ascending order.` ` ` `arr.Sort();` ` ` `brr.Sort();` ` ` `arr.Reverse();` ` ` `int` `cnt = 0;` ` ` `// Count the number of sets with size 1` ` ` `foreach` `(` `int` `v ` `in` `brr) {` ` ` `if` `(v == 1)` ` ` `cnt++;` ` ` `}` ` ` `// Assign the first K maximum elements` ` ` `// to the sets and add them as minimum` ` ` `// also for sets with size 1.` ` ` `for` `(` `int` `i = 0; i < k; i++) {` ` ` `ans += arr[i];` ` ` `if` `(cnt > 0) {` ` ` `ans += arr[i];` ` ` `cnt--;` ` ` `}` ` ` `}` ` ` `int` `from` `= k;` ` ` `// Add the minimum element from the set.` ` ` `for` `(` `int` `i = 0; i < k; i++) {` ` ` `if` `(brr[i] == 1)` ` ` `continue` `;` ` ` `ans += arr[` `from` `+ brr[i] - 2];` ` ` `from` `+= brr[i] - 1;` ` ` `}` ` ` `Console.Write(ans);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `n, k;` ` ` `n = 4;` ` ` `k = 2;` ` ` `List<` `int` `> arr = ` `new` `List<` `int` `>(){ 10, 10, 11, 11 };` ` ` `List<` `int` `> brr = ` `new` `List<` `int` `>(){ 2, 2 };` ` ` `findSets(n, k, arr, brr);` `}` `}` `// This code is contributed by SURENDRA_GANGWAR.` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approach` ` ` `// Function to find K sets such that the` ` ` `// sum of maximum and minimum of all sets` ` ` `// is maximum` ` ` `function` `findSets(n, k, arr, brr)` ` ` `{` ` ` `let ans = 0;` ` ` `// Sort both the arrays` ` ` `// arr[] in descending order.` ` ` `// brr[] in ascending order.` ` ` `arr.sort((a, b) => a - b);` ` ` `brr.sort((a, b) => a - b);` ` ` `arr.reverse();` ` ` `let cnt = 0;` ` ` `// Count the number of sets with size 1` ` ` `for` `(let v of brr) {` ` ` `if` `(v == 1)` ` ` `cnt++;` ` ` `}` ` ` `// Assign the first K maximum elements` ` ` `// to the sets and add them as minimum` ` ` `// also for sets with size 1.` ` ` `for` `(let i = 0; i < k; i++) {` ` ` `ans += arr[i];` ` ` `if` `(cnt > 0) {` ` ` `ans += arr[i];` ` ` `cnt--;` ` ` `}` ` ` `}` ` ` `let from = k;` ` ` `// Add the minimum element from the set.` ` ` `for` `(let i = 0; i < k; i++) {` ` ` `if` `(brr[i] == 1)` ` ` `continue` `;` ` ` `ans += arr[from + brr[i] - 2];` ` ` `from += brr[i] - 1;` ` ` `}` ` ` `document.write(ans);` ` ` `}` ` ` `// Driver Code` ` ` `let n, k;` ` ` `n = 4;` ` ` `k = 2;` ` ` `let arr = [10, 10, 11, 11];` ` ` `let brr = [2, 2];` ` ` `findSets(n, k, arr, brr);` ` ` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

42

**Time Complexity: **O(N*log(N))**Auxiliary Space: **O(1)

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**.