Given an array arr[] of size N, two positive integers M and K, the task is to partition the array into M equal length subsets such that the sum of the Kth largest element of all these subsets is maximum. If it is not possible to partition the array into M equal length subsets, then print -1.
Examples:
Input: arr[] = { 1, 2, 3, 4, 5, 6 }, M = 2, K = 2
Output: 8
Explanation:
Length of each subset = (N / M) = 3.
Possible subsets from the array are: { {1, 3, 4}, {2, 5, 6} }
Therefore, the sum of Kth largest element from each subset = 3 + 5 = 8Input: arr[] = {11, 20, 2, 17}, M = 4, K = 1
Output: 50
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- If N is not divisible M, then print -1.
- Initialize a variable, say maxSum, to store the maximum possible sum of Kth largest element of all the subsets of the array by partitioning the array into M equal length subset.
- Sort the array in descending order.
- Iterate over the range [1, M] using variable i and update maxSum += arr[i * K – 1].
- Finally, print the value of maxSum.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of Kth// largest element of M equal length partitionint maximumKthLargestsumPart(int arr[], int N, int M, int K){ // Stores sum of K_th largest element // of equal length partitions int maxSum = 0; // If N is not // divisible by M if (N % M) return -1; // Stores length of // each partition int sz = (N / M); // If K is greater than // length of partition if (K > sz) return -1; // Sort array in // descending porder sort(arr, arr + N, greater<int>()); // Traverse the array for (int i = 1; i <= M; i++) { // Update maxSum maxSum += arr[i * K - 1]; } return maxSum;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int M = 2; int K = 1; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumKthLargestsumPart(arr, N, M, K); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;import java.util.Collections;class GFG{ // Function to find the maximum sum of Kth // largest element of M equal length partition static int maximumKthLargestsumPart(int[] arr, int N, int M, int K) { // Stores sum of K_th largest element // of equal length partitions int maxSum = 0; // If N is not // divisible by M if (N % M != 0) return -1; // Stores length of // each partition int sz = (N / M); // If K is greater than // length of partition if (K > sz) return -1; // Sort array in // descending porder Arrays.sort(arr); int i, k, t; for(i = 0; i < N / 2; i++) { t = arr[i]; arr[i] = arr[N - i - 1]; arr[N - i - 1] = t; } // Traverse the array for(i = 1; i <= M; i++) { // Update maxSum maxSum += arr[i * K - 1]; } return maxSum; } // Driver codepublic static void main(String[] args){ int[] arr = { 1, 2, 3, 4, 5, 6 }; int M = 2; int K = 1; int N = arr.length; System.out.println(maximumKthLargestsumPart( arr, N, M, K)); }} // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement# the above approach# Function to find the maximum sum of Kth# largest element of M equal length partitiondef maximumKthLargestsumPart(arr, N, M, K): # Stores sum of K_th largest element # of equal length partitions maxSum = 0 # If N is not # divisible by M if (N % M != 0): return -1 # Stores length of # each partition sz = (N / M) # If K is greater than # length of partition if (K > sz): return -1 # Sort array in # descending porder arr = sorted(arr) for i in range(0, N // 2): t = arr[i] arr[i] = arr[N - i - 1] arr[N - i - 1] = t # Traverse the array for i in range(1, M + 1): # Update maxSum maxSum += arr[i * K - 1] return maxSum# Driver codeif __name__ == '__main__': arr = [ 1, 2, 3, 4, 5, 6 ] M = 2 K = 1 N = len(arr) print(maximumKthLargestsumPart(arr, N, M, K))# This code is contributed by Amit Katiyar |
C#
// C# program to implement // the above approach using System;class GFG{ // Function to find the maximum sum of Kth // largest element of M equal length partition static int maximumKthLargestsumPart(int[] arr, int N, int M, int K) { // Stores sum of K_th largest element // of equal length partitions int maxSum = 0; // If N is not // divisible by M if (N % M != 0) return -1; // Stores length of // each partition int sz = (N / M); // If K is greater than // length of partition if (K > sz) return -1; // Sort array in // descending porder Array.Sort(arr); Array.Reverse(arr); // Traverse the array for(int i = 1; i <= M; i++) { // Update maxSum maxSum += arr[i * K - 1]; } return maxSum; }// Driver code static void Main(){ int[] arr = { 1, 2, 3, 4, 5, 6 }; int M = 2; int K = 1; int N = arr.Length; Console.WriteLine(maximumKthLargestsumPart( arr, N, M, K)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// javascript program to implement// the above approach// Function to find the maximum sum of Kth// largest element of M equal length partitionfunction maximumKthLargestsumPart(arr, N, M, K){ // Stores sum of K_th largest element // of equal length partitions let maxSum = 0; // If N is not // divisible by M if (N % M != 0) return -1; // Stores length of // each partition let sz = (N / M); // If K is greater than // length of partition if (K > sz) return -1; // Sort array in // descending porder arr.sort(); let i, k, t; for(i = 0; i < N / 2; i++) { t = arr[i]; arr[i] = arr[N - i - 1]; arr[N - i - 1] = t; } // Traverse the array for(i = 1; i <= M; i++) { // Update maxSum maxSum += arr[i * K - 1]; } return maxSum;} // Driver code let arr = [ 1, 2, 3, 4, 5, 6 ]; let M = 2; let K = 1; let N = arr.length; document.write(maximumKthLargestsumPart( arr, N, M, K)); // This code is contributed by splevel62.</script> |
Output:
11
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!
