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: 42
Explanation: 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.
- 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.
- 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 maximumvoid 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 Codeint 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 approachclass 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 maximumdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to find K sets such that the// sum of maximum and minimum of all sets// is maximumstatic 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 Codepublic 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)
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!
Share your thoughts in the comments
