Given an array arr[] consisting of N integers and an integer K, the task is to split the given array into K non-overlapping subsets such that the maximum among the sum of all subsets is minimum.
Examples:
Input: arr[] = {1, 7, 9, 2, 12, 3, 3}, M = 3
Output: 13
Explanation:
One possible way to split the array into 3 non-overlapping subsets is {arr[4], arr[0]}, {arr[2], arr[6]}, and {arr[1], arr[5], arr[3]}.
The sum of each subset is 13, 12 and 12 respectively. Now, the maximum among all the sum of subsets is 13, which is the minimum possible sum.Input: arr[] = {1, 2, 3, 4, 5}, M = 2
Output: 8
Approach: The given problem can be solved by the Greedy Approach by using the priority queue and sorting the given array. Follow the steps below to solve the problem:
- Initialize a Min-Heap using priority_queue say PQ to store the sum of elements of each group.
- Iterate in the range [1, K] and push 0 into the PQ.
- Sort the array, arr[] in decreasing order.
- Traverse the array arr[] and for each array elements arr[i], add the element arr[i] to the smallest sum group which will be at the top of the priority queue PQ.
- After completing the above steps, print the last element of the priority queue PQ as the resultant minimized maximum sum among all the possible groups.
Below is the implementation of the above approach:
+++++
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to split the array into M// groups such that maximum of the sum// of all elements of all the groups// is minimizedint findMinimumValue(int arr[], int N, int M){ // Sort the array in decreasing order sort(arr, arr + N, greater<int>()); // Initialize priority queue (Min heap) priority_queue<int, vector<int>, greater<int> > pq; // Push 0 for all the M groups for (int i = 1; i <= M; ++i) { pq.push(0); } // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Pop the group having the // minimum sum int val = pq.top(); pq.pop(); // Increment val by arr[i] val += arr[i]; // Push the new sum of the // group into the pq pq.push(val); } // Iterate while size of the pq // is greater than 1 while (pq.size() > 1) { pq.pop(); } // Return result return pq.top();}// Driver Codeint main(){ int arr[] = { 1, 7, 9, 2, 12, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; cout << findMinimumValue(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Function to split the array into M // groups such that maximum of the sum // of all elements of all the groups // is minimized static int findMinimumValue(Vector<Integer> arr, int N, int M) { // Sort the array in decreasing order Collections.sort(arr); Collections.reverse(arr); // Initialize priority queue (Min heap) Vector<Integer> pq = new Vector<Integer>(); // Push 0 for all the M groups for (int i = 1; i <= M; ++i) { pq.add(0); } Collections.sort(pq); // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Pop the group having the // minimum sum int val = pq.get(0); pq.remove(0); // Increment val by arr[i] val += arr.get(i); // Push the new sum of the // group into the pq pq.add(val); Collections.sort(pq); } // Iterate while size of the pq // is greater than 1 while (pq.size() > 1) { pq.remove(0); } // Return result return pq.get(0); } public static void main(String[] args) { Integer[] arr = { 1, 7, 9, 2, 12, 3, 3 }; Vector<Integer> Arr = new Vector<Integer>(); Collections.addAll(Arr, arr); int N = Arr.size(); int K = 3; System.out.println(findMinimumValue(Arr, N, K)); }}// This code is contributed by divyesh072019. |
Python3
# Python3 program for the above approach# Function to split the array into M# groups such that maximum of the sum# of all elements of all the groups# is minimizeddef findMinimumValue(arr, N, M): # Sort the array in decreasing order arr.sort() arr.reverse() # Initialize priority queue (Min heap) pq = [] # Push 0 for all the M groups for i in range(1, M + 1): pq.append(0) pq.sort() # Traverse the array, arr[] for i in range(N): # Pop the group having the # minimum sum val = pq[0] del pq[0] # Increment val by arr[i] val += arr[i] # Push the new sum of the # group into the pq pq.append(val) pq.sort() # Iterate while size of the pq # is greater than 1 while (len(pq) > 1) : del pq[0] # Return result return pq[0]arr = [ 1, 7, 9, 2, 12, 3, 3 ]N = len(arr)K = 3print(findMinimumValue(arr, N, K))# This code is contributed by suresh07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to split the array into M // groups such that maximum of the sum // of all elements of all the groups // is minimized static int findMinimumValue(int[] arr, int N, int M) { // Sort the array in decreasing order Array.Sort(arr); Array.Reverse(arr); // Initialize priority queue (Min heap) List<int> pq = new List<int>(); // Push 0 for all the M groups for (int i = 1; i <= M; ++i) { pq.Add(0); } pq.Sort(); // Traverse the array, arr[] for (int i = 0; i < N; ++i) { // Pop the group having the // minimum sum int val = pq[0]; pq.RemoveAt(0); // Increment val by arr[i] val += arr[i]; // Push the new sum of the // group into the pq pq.Add(val); pq.Sort(); } // Iterate while size of the pq // is greater than 1 while (pq.Count > 1) { pq.RemoveAt(0); } // Return result return pq[0]; } static void Main() { int[] arr = { 1, 7, 9, 2, 12, 3, 3 }; int N = arr.Length; int K = 3; Console.Write(findMinimumValue(arr, N, K)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Function to split the array into M // groups such that maximum of the sum // of all elements of all the groups // is minimized function findMinimumValue(arr, N, M) { // Sort the array in decreasing order arr.sort(function(a, b){return a - b}); arr.reverse(); // Initialize priority queue (Min heap) let pq = []; // Push 0 for all the M groups for (let i = 1; i <= M; ++i) { pq.push(0); } pq.sort(function(a, b){return a - b}); // Traverse the array, arr[] for (let i = 0; i < N; ++i) { // Pop the group having the // minimum sum let val = pq[0]; pq.shift(); // Increment val by arr[i] val += arr[i]; // Push the new sum of the // group into the pq pq.push(val); pq.sort(function(a, b){return a - b}); } // Iterate while size of the pq // is greater than 1 while (pq.length > 1) { pq.shift(); } // Return result return pq[0]; } let arr = [ 1, 7, 9, 2, 12, 3, 3 ]; let N = arr.length; let K = 3; document.write(findMinimumValue(arr, N, K)); // This code is contributed by decode2207.</script> |
Output:
13
Time Complexity: O(N*log K)
Auxiliary Space: O(M)
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!
