Minimize sum of differences between maximum and minimum elements present in K subsets
Given an array arr[] of size N and an integer K, the task is to minimize the sum of the difference between the maximum and minimum element of each subset by splitting the array into K subsets such that each subset consists of unique array elements only.
Examples:
Input: arr[] = { 6, 3, 8, 1, 3, 1, 2, 2 }, K = 4 Output: 6 Explanation: One of the optimal ways to split the array into K(= 4) subsets are { { 1, 2 }, { 2, 3 }, { 6, 8 }, { 1, 4 } }. Sum of difference of maximum and minimum element present in each subset = { (2 – 1) + (3 – 2) + (8 – 6) + (3 – 1) } = 6. Therefore, the required output is 6
Input: arr[] = { 2, 2, 1, 1 }, K = 1 Output: -1
Approach: The problem can be solved using Dynamic Programming with bitmasking. Following are the recurrence relations:
mask: ith bit of mask checks if array element is already selected in a subset or not. l: index of last element selected in a subset. j: index of current element selected in a subset.
If count of set bits in mask mod (N / K) == 1: dp[mask][l] = min(dp[mask][l], dp[mask ^ (1 << l)][j])
Otherwise, dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][l] + nums[l] – nums[j])
Follow the steps below to solve the problem:
- Iterate over all possible values of mask, i.e. [0, 2N – 1]
- Initialize an array, say n_z_bits[], to store the count of elements already selected in subsets.
- Use the above recurrence relation and fill all possible dp states of the recurrence relation.
- Finally, print the minimum elements from dp[(1 << N ) – 1].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to minimize the sum of // difference between maximums and // minimums of K subsets of an array int MinimizeSum(vector< int >& nums, int k) { // Stores count of elements // in an array int n = nums.size(); // Base Case if (k == n) return 0; // Initialize DP[][] array int inf = 1e9; vector<vector< int > > dp(1 << n, vector< int >(n, inf)); // Sort the array sort(nums.begin(), nums.end()); // Mark i-th element as not selected for ( int i = 0; i < n; i++) { dp[1 << i][i] = 0; } // Iterate over all possible // values of mask for ( int mask = 0; mask < (1 << n); mask++) { // Store count of set bits // in mask vector< int > n_z_bits; // Store index of element which is // already selected in a subset for ( int i = 0; i < n; i++) { if ((mask >> i) & 1) { n_z_bits.push_back(i); } } // If count of set bits in mask mod (n // k) equal // to 1 if (n_z_bits.size() % (n / k) == 1) { for ( int i = 0; i < n_z_bits.size(); i++) { for ( int j = i + 1; j < n_z_bits.size(); j++) { int temp = dp[mask ^ (1 << n_z_bits[j])] [n_z_bits[i]]; dp[mask][n_z_bits[j]] = min(dp[mask][n_z_bits[j]], temp); } } } else { for ( int i = 0; i < n_z_bits.size(); i++) { for ( int j = i + 1; j < n_z_bits.size(); j++) { if (nums[n_z_bits[i]] != nums[n_z_bits[j]]) { // Check if l-th element // is already selected or not int mask_t = mask ^ (1 << n_z_bits[j]); int temp = (dp[mask_t][n_z_bits[i]] + nums[n_z_bits[i]] - nums[n_z_bits[j]]); // Update dp[mask][l] dp[mask][n_z_bits[j]] = min( dp[mask][n_z_bits[j]], temp); } } } } } // Return minimum element // from dp[(1 << N) - 1] int minVal = inf; for ( int i = 0; i < n; i++) { minVal = min(minVal, dp[(1 << n) - 1][i]); } // If dp[-1] is inf then the // partition is not possible if (minVal == inf) { return -1; } else { return 999999999- minVal; } } // Driver Code int main() { // Given array vector< int > arr = { 6, 3, 8, 1, 3, 1, 2, 2 }; int k = 4; // Function call cout << MinimizeSum(arr, k) << endl; return 0; } // This code is contributed by lokeshpotta20. |
Java
import java.util.*; public class GFG { // Function to minimize the sum of // difference between maximums and // minimums of K subsets of an array public static int MinimizeSum(List<Integer> nums, int k) { // Stores count of elements // in an array int n = nums.size(); //Base Case if (k == n) { return 0 ; } // Initialize DP[][] array int inf = 1_000_000_000; int [][] dp = new int [ 1 << n][n]; for ( int [] row : dp) { java.util.Arrays.fill(row, inf); } // Sort the array Collections.sort(nums); // Mark i-th element as not selected for ( int i = 0 ; i < n; i++) { dp[ 1 << i][i] = 0 ; } // Iterate over all possible // values of mask for ( int mask = 0 ; mask < ( 1 << n); mask++) { // Store count of set bits // in mask List<Integer> n_z_bits = new ArrayList<>(); // Store index of element which is // already selected in a subset for ( int i = 0 ; i < n; i++) { if ((mask >> i & 1 ) == 1 ) { n_z_bits.add(i); } } // If count of set bits in mask mod (n // k) equal // to 1 if (n_z_bits.size() % (n / k) == 1 ) { for ( int i = 0 ; i < n_z_bits.size(); i++) { for ( int j = i + 1 ; j < n_z_bits.size(); j++) { int temp = dp[mask ^ ( 1 << n_z_bits.get(j))][n_z_bits.get(i)]; dp[mask][n_z_bits.get(j)] = Math.min(dp[mask][n_z_bits.get(j)], temp); } } } else { for ( int i = 0 ; i < n_z_bits.size(); i++) { for ( int j = i + 1 ; j < n_z_bits.size(); j++) { if (nums.get(n_z_bits.get(i)) != nums.get(n_z_bits.get(j))) { // Check if l-th element // is already selected or not int maskT = mask ^ ( 1 << n_z_bits.get(j)); int temp = (dp[maskT][n_z_bits.get(i)] + nums.get(n_z_bits.get(i)) - nums.get(n_z_bits.get(j))); // Update dp[mask][l] dp[mask][n_z_bits.get(j)] = Math.min(dp[mask][n_z_bits.get(j)], temp); } } } } } // Return minimum element // from dp[(1 << N) - 1] int minVal = inf; // If dp[-1] is inf then the // partition is not possible for ( int i = 0 ; i < n; i++) { minVal = Math.min(minVal, dp[( 1 << n) - 1 ][i]); } if (minVal == inf) { return - 1 ; } else { return 999999999 - minVal; } } public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add( 6 );arr.add( 3 );arr.add( 8 );arr.add( 1 ); arr.add( 3 );arr.add( 1 );arr.add( 2 );arr.add( 2 ); int k = 4 ; System.out.println(MinimizeSum(arr,k)); } } // This code is contributed by anskalyan3. |
Python3
# Python program to implement # the above approach from itertools import permutations from itertools import combinations # Function to minimize the sum of # difference between maximums and # minimums of K subsets of an array def MinimizeSum(nums, k): # Stores count of elements # in an array n = len (nums) # Base Case if k = = n: return 0 # Initialize DP[][] array dp = [[ float ( "inf" )] * n for _ in range ( 1 << n)] # Sort the array nums.sort() # Mark i-th element # as not selected for i in range (n): dp[ 1 << i][i] = 0 # Iterate over all possible # values of mask for mask in range ( 1 << n): # Store count of set bits # in mask n_z_bits = [] # Store index of element which is # already selected in a subset for p, c in enumerate ( bin (mask)): if c = = "1" : temp = len ( bin (mask)) - p - 1 n_z_bits.append(temp) # If count of set bits in mask # mod (n // k) equal to 1 if len (n_z_bits) % (n / / k) = = 1 : for j, l in permutations(n_z_bits, 2 ): temp = dp[mask ^ ( 1 << l)][j] dp[mask][l] = min (dp[mask][l], temp) else : for j, l in combinations(n_z_bits, 2 ): if nums[j] ! = nums[l]: # Check if l-th element # is already selected or not mask_t = mask ^ ( 1 << l) temp = (dp[mask_t][j] + nums[j] - nums[l]) # Update dp[mask][l] dp[mask][l] = min (dp[mask][l], temp) # Return minimum element # from dp[(1 << N) - 1] if min (dp[ - 1 ]) ! = float ( "inf" ): return min (dp[ - 1 ]) # If dp[-1] is inf then the # partition is not possible else : return - 1 # Driver Code if __name__ = = "__main__" : # Given array arr = [ 6 , 3 , 8 , 1 , 3 , 1 , 2 , 2 ] K = 4 # Function call print (MinimizeSum(arr, K)) |
C#
using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to minimize the sum of // difference between maximums and // minimums of K subsets of an array public static int MinimizeSum(List< int > nums, int k) { // Stores count of elements // in an array int n = nums.Count; if (k == n) { return 0; } // Initialize DP[][] array int inf = 1_000_000_000; int [][] dp = new int [1 << n][]; for ( int i = 0; i < dp.Length; i++) { dp[i] = new int [n]; for ( int j = 0; j < n; j++) { dp[i][j] = inf; } } // Sort the array nums.Sort(); // Mark i-th element as not selected for ( int i = 0; i < n; i++) { dp[1 << i][i] = 0; } // Iterate over all possible // values of mask for ( int mask = 0; mask < (1 << n); mask++) { // Store count of set bits // in mask List< int > n_z_bits = new List< int >(); // Store index of element which is // already selected in a subset for ( int i = 0; i < n; i++) { if ((mask >> i & 1) == 1) { n_z_bits.Add(i); } } // If count of set bits in mask mod (n // k) // equal // to 1 if (n_z_bits.Count % (n / k) == 1) { for ( int i = 0; i < n_z_bits.Count; i++) { for ( int j = i + 1; j < n_z_bits.Count; j++) { int temp = dp[mask ^ (1 << n_z_bits[j])] [n_z_bits[i]]; dp[mask][n_z_bits[j]] = Math.Min( dp[mask][n_z_bits[j]], temp); } } } else { for ( int i = 0; i < n_z_bits.Count; i++) { for ( int j = i + 1; j < n_z_bits.Count; j++) { if (nums[n_z_bits[i]] != nums[n_z_bits[j]]) { int maskT = mask ^ (1 << n_z_bits[j]); int temp = (dp[maskT][n_z_bits[i]] + nums[n_z_bits[i]] - nums[n_z_bits[j]]); dp[mask][n_z_bits[j]] = Math.Min( dp[mask][n_z_bits[j]], temp); } } } } } // Return minimum element // from dp[(1 << N) - 1] int minVal = inf; for ( int i = 0; i < n; i++) { minVal = Math.Min(minVal, dp[(1 << n) - 1][i]); } // If dp[-1] is inf then the // partition is not possible if (minVal == inf) { return -1; } else { return 999999999 - minVal; } } // Driver Code static void Main( string [] args) { // Given array List< int > arr = new List< int >{ 6, 3, 8, 1, 3, 1, 2, 2 }; int k = 4; Console.WriteLine(MinimizeSum(arr, k)); } // This code is contributed by Aditya Sharma. } |
Javascript
// Javascript equivalent // Function to minimize the sum of // difference between maximums and // minimums of K subsets of an array function MinimizeSum(nums, k) { // Stores count of elements // in an array let n = nums.length; //Base Case if (k == n) { return 0; } // Initialize DP[][] array let inf = 1000000000; let dp = new Array(1 << n); for (let i = 0; i < dp.length; i++) { dp[i] = Array(n).fill(inf); } // Sort the array nums.sort((a, b) => a - b); // Mark i-th element as not selected for (let i = 0; i < n; i++) { dp[1 << i][i] = 0; } // Iterate over all possible // values of mask for (let mask = 0; mask < (1 << n); mask++) { // Store count of set bits // in mask let n_z_bits = []; // Store index of element which is // already selected in a subset for (let i = 0; i < n; i++) { if ((mask >> i & 1) == 1) { n_z_bits.push(i); } } // If count of set bits in mask mod (n // k) equal // to 1 if (n_z_bits.length % (n / k) == 1) { for (let i = 0; i < n_z_bits.length; i++) { for (let j = i + 1; j < n_z_bits.length; j++) { let temp = dp[mask ^ (1 << n_z_bits[j])][n_z_bits[i]]; dp[mask][n_z_bits[j]] = Math.min( dp[mask][n_z_bits[j]], temp ); } } } else { for (let i = 0; i < n_z_bits.length; i++) { for (let j = i + 1; j < n_z_bits.length; j++) { if (nums[n_z_bits[i]] != nums[n_z_bits[j]]) { // Check if l-th element // is already selected or not let maskT = mask ^ (1 << n_z_bits[j]); let temp = dp[maskT][n_z_bits[i]] + nums[n_z_bits[i]] - nums[n_z_bits[j]]; // Update dp[mask][l] dp[mask][n_z_bits[j]] = Math.min( dp[mask][n_z_bits[j]], temp ); } } } } } // Return minimum element // from dp[(1 << N) - 1] let minVal = inf; // If dp[-1] is inf then the // partition is not possible for (let i = 0; i < n; i++) { minVal = Math.min(minVal, dp[(1 << n) - 1][i]); } if (minVal == inf) { return -1; } else { return 999999999 - minVal; } } let arr = [6,3,8,1,3,1,2,2]; let k = 4; console.log(MinimizeSum(arr,k)); |
6
Time Complexity: O(N^2 * 2N)
Auxiliary Space: O(N^2 * 2N)
/* Complexity Analysis corrected by RainX */