Given an array arr[] consisting of N integers and an integer K, the task is to find the minimum sum of incompatibilities of K subsets of equal sizes having unique elements.
The difference between the maximum and the minimum element in a set is known as the incompatibility of a set.
Examples:
Input: arr[] = {1, 2, 1, 4}, K = 2
Output: 4
Explanation:
One of the possible ways of distributing the array into K(i.e., 2) subsets is {1, 2} and {1, 4}.
The incompatibility of the first subset = (2 – 1) = 1.
The incompatibility of the second subset = (4 – 1) = 3.
Therefore, the total sum of incompatibilities of both subsets = 1 + 3 = 4, which is the minimum among all possibilities.Input: arr[] = {6, 3, 8, 1, 3, 1, 2, 2}, K = 4
Output: 6
Explanation:
One of the possible ways of distributing the array into K subset is: {1, 2}, {2, 3}, {6, 8}, {1, 3}.
The incompatibility of the first subset = (2-1) = 1.
The incompatibility of the second subset = (3-2) = 1.
The incompatibility of the third subset = (8-6) = 2.
The incompatibility of the fourth subset = (3-1) = 2.
Therefore, total sum of incompatibilities of K subset = 1 + 1 + 2 + 2 = 6. And it is also the minimum among all possibilities
Naive Approach: The simplest approach is to traverse the given array recursively and in each recursion traverse over all possible ways of selecting N/K elements of the array using bitmask and calculate the incompatibility of that subset and then return the minimum among all.
Time Complexity: O(N*23*N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using dynamic programming. The given problem can be solved based on the following observations:
- It can be observed that it requires a 2 state Dynamic programming with Bitmasking say DP(mask, i) to solve the problem where i represents the current position of the array and each binary bit of mask represent if the element has been already selected or not.
- The transition state will include calculating the incompatibility by selecting a subset of size N/K.
- Suppose X and Y is minimum and maximum of current set and newmask is another variable with value initially as the mask
- Now, mark all the N/K elements that have been selected occurs only once in newmask then DP(mask, i) is calculated by (Y – X + min(DP(newmask, i + 1), DP(mask, i))).
Follow the steps below to solve the problem:
- Initialize a 2D array, say dp[][].
- Define a recursive function, say dfs (mask, i), to calculate the result:
- Base Case: If i > K, then return 0.
- Check if dp[mask][i] != -1, then return dp[mask][i] as the current state is already calculated.
- Select N/K elements from the array using bitmasking and if it possible to choose i elements of the subset which only occurs once and are not already part of other subsets, then update the current dp state as:
dp[mask][i] = min(dp[mask][i], Y – X + dfs(newmask, i))
- Return the value of dp[mask][i] as the result in the current recursive call.
- Call the recursive function dfs(2N-1, 0) and print the value returned by it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int k;int n;int goal;vector<vector<int>> dp;vector<int> bits;// Recursive function to find// the minimum required valueint dfs(vector<int> A, int state,int index){ // Base Case if (index >= k) { return 0; } // Stores the minimum value // of the current state int res = 1000; // If dp[state][index] is // already calculated if (dp[state][index] != -1) { // return dp[state][index] return dp[state][index]; } // Traverse over all the bits for (int bit : bits) { // If count of set bit is N/K if (__builtin_popcount(bit) == goal) { // Store the new state after // choosing N/K elements int newstate = state; // Stores the minimum and // maximum of current subset int mn = 100, mx = -1; // Stores if the elements // have been already // selected or not vector<bool> visit(n+1,false); // Stores if it is possible // to select N/K elements bool good = true; // Traverse over the array for (int j = 0; j < n; j++) { // If not chosen already // for another subset if ((bit & (1 << j)) != 0) { // If already chosen // for another subset // or current subset if (visit[A[j]] == true || (state & (1 << j)) == 0) { // Mark the good false good = false; break; } // Mark the current // number visited visit[A[j]] = true; // Mark the current // position in mask // newstate newstate = newstate ^ (1 << j); // Update the maximum // and minimum mx = max(mx, A[j]); mn = min(mn, A[j]); } } // If good is true then // Update the res if (good) { res = min( res, mx - mn + dfs(A, newstate, index + 1)); } } } // Update the current sp state dp[state][index] = res; // Return the res return res;}// Function to find the minimum// incompatibility sumint minimumIncompatibility(vector<int> A, int K){ n = A.size(); k = K; goal = n / k; // Stores the count of element map<int, int> mp; // Traverse the array for (int i : A) { // If number i not occurs // in Map if (mp.find(i)==mp.end()){ // Put the element // in the Map mp[i] = 0; } // Increment the count of // i in the Hash Map mp[i]++; // If count of i in Map is // greater than K then // return -1 if (mp[i] > k) return -1; } // Stores all total state int state = (1 << n) - 1; // Traverse over all the state for (int i = 0; i <= state; i++) { // If number of set bit // is equal to N/K if (__builtin_popcount(i) == goal){ bits.push_back(i); } } // Stores the minimum value // at a state dp.resize(1<<n,vector<int>(k,-1)); // Initialize the dp state // with -1 // for (int i = 0; // i < dp.ize(); i++) { // Arrays.fill(dp[i], -1); // } // Call the recursive function return dfs(A, state, 0);}// Driver codeint main(){ vector<int> arr = { 1, 2, 1, 4 }; int K = 2; // Function Call cout<<(minimumIncompatibility(arr, K));}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class Solution { int k; int n; int goal; int dp[][]; List<Integer> bits = new ArrayList<>(); // Function to find the minimum // incompatibility sum public int minimumIncompatibility( int[] A, int k) { this.n = A.length; this.k = k; goal = n / k; // Stores the count of element Map<Integer, Integer> map = new HashMap<>(); // Traverse the array for (int i : A) { // If number i not occurs // in Map if (!map.containsKey(i)) // Put the element // in the Map map.put(i, 0); // Increment the count of // i in the Hash Map map.put(i, map.get(i) + 1); // If count of i in Map is // greater than K then // return -1 if (map.get(i) > k) return -1; } // Stores all total state int state = (1 << n) - 1; // Traverse over all the state for (int i = 0; i <= state; i++) { // If number of set bit // is equal to N/K if (Integer.bitCount(i) == goal) bits.add(i); } // Stores the minimum value // at a state dp = new int[1 << n][k]; // Initialize the dp state // with -1 for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], -1); } // Call the recursive function return dfs(A, state, 0); } // Recursive function to find // the minimum required value public int dfs(int A[], int state, int index) { // Base Case if (index >= k) { return 0; } // Stores the minimum value // of the current state int res = 1000; // If dp[state][index] is // already calculated if (dp[state][index] != -1) { // return dp[state][index] return dp[state][index]; } // Traverse over all the bits for (int bit : bits) { // If count of set bit is N/K if (Integer.bitCount(bit) == goal) { // Store the new state after // choosing N/K elements int newstate = state; // Stores the minimum and // maximum of current subset int mn = 100, mx = -1; // Stores if the elements // have been already // selected or not boolean visit[] = new boolean[n + 1]; // Stores if it is possible // to select N/K elements boolean good = true; // Traverse over the array for (int j = 0; j < n; j++) { // If not chosen already // for another subset if ((bit & (1 << j)) != 0) { // If already chosen // for another subset // or current subset if (visit[A[j]] == true || (state & (1 << j)) == 0) { // Mark the good false good = false; break; } // Mark the current // number visited visit[A[j]] = true; // Mark the current // position in mask // newstate newstate = newstate ^ (1 << j); // Update the maximum // and minimum mx = Math.max(mx, A[j]); mn = Math.min(mn, A[j]); } } // If good is true then // Update the res if (good) { res = Math.min( res, mx - mn + dfs(A, newstate, index + 1)); } } } // Update the current sp state dp[state][index] = res; // Return the res return res; }}// Driver Codeclass GFG { public static void main(String[] args) { Solution st = new Solution(); int[] arr = { 1, 2, 1, 4 }; int K = 2; // Function Call System.out.print( st.minimumIncompatibility(arr, K)); }} |
Python3
# Python program for the above approach:k = 0n = 0goal = 0dp = []bits = []def __builtin_popcount(n): count = 0 while (n > 0): count += (n & 1) n >>= 1 return count## Recursive function to find## the minimum required valuedef dfs(A, state, index): global k global n global goal global dp global bits ## Base Case if (index >= k): return 0; ## Stores the minimum value ## of the current state res = 1000 ## If dp[state][index] is ## already calculated if (dp[state][index] != -1): ## return dp[state][index] return dp[state][index]; ## Traverse over all the bits for bit in bits: ## If count of set bit is N/K if (__builtin_popcount(bit) == goal): ## Store the new state after ## choosing N/K elements newstate = state; ## Stores the minimum and ## maximum of current subset mn = 100 mx = -1 ## Stores if the elements ## have been already ## selected or not visit = [False]*(n+1) ## Stores if it is possible ## to select N/K elements good = True ## Traverse over the array for j in range(0, n): ## If not chosen already ## for another subset if ((bit & (1 << j)) != 0): ## If already chosen ## for another subset ## or current subset if (visit[A[j]] == True or (state & (1 << j)) == 0): ## Mark the good false good = False; break; ## Mark the current ## number visited visit[A[j]] = True; ## Mark the current ## position in mask ## newstate newstate = newstate ^ (1 << j); ## Update the maximum ## and minimum mx = max(mx, A[j]) mn = min(mn, A[j]) ## If good is True then ## Update the res if (good): res = min(res, mx - mn + dfs(A, newstate, index + 1)) ## Update the current sp state dp[state][index] = res ## Return the res return res## Function to find the minimum## incompatibility sumdef minimumIncompatibility(A, K): global k global n global goal global dp global bits n = len(A) k = K goal = n // k ## Stores the count of element mp = {} ## Traverse the array for i in A: ## If number i not occurs ## in Map if (i not in mp): ## Put the element ## in the Map mp[i] = 0 ## Increment the count of ## i in the Hash Map mp[i]+=1 ## If count of i in Map is ## greater than K then ## return -1 if (mp[i] > k): return -1; ## Stores all total state state = (1 << n) - 1; ## Traverse over all the state for i in range(state + 1): ## If number of set bit ## is equal to N/K if (__builtin_popcount(i) == goal): bits.append(i) ## Stores the minimum value ## at a state for i in range(1 << n): dp.append([]) for j in range(k): dp[i].append(-1) ## Call the recursive function return dfs(A, state, 0);## Driver codeif __name__=='__main__': arr = [ 1, 2, 1, 4 ] K = 2 ## Function Call print(minimumIncompatibility(arr, K)) # This code is contributed by subhamgoyal2014. |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;using System.Linq;class Solution { int k; int n; int goal; int [,]dp; List<int> bits = new List<int>(); // Function to find the minimum // incompatibility sum public int minimumIncompatibility( int[] A, int k) { this.n = A.Length; this.k = k; goal = n / k; // Stores the count of element Dictionary<int,int> map = new Dictionary<int,int>(); // Traverse the array foreach(int i in A) { // If number i not occurs // in Map if (!map.ContainsKey(i)) // Put the element // in the Map map[i]= 0; // Increment the count of // i in the Hash Map map[i]++; // If count of i in Map is // greater than K then // return -1 if (map[i] > k) return -1; } // Stores all total state int state = (1 << n) - 1; // Traverse over all the state for (int i = 0; i <= state; i++) { // If number of set bit // is equal to N/K if (Convert.ToString(i, 2).Count(c => c == '1') == goal) bits.Add(i); } // Stores the minimum value // at a state dp = new int[1 << n,k]; // Initialize the dp state // with -1 for (int i = 0;i < dp.GetLength(0); i++) { for (int j = 0;j < dp.GetLength(1); j++) { dp[i,j]=-1; } } // Call the recursive function return dfs(A, state, 0); } // Recursive function to find // the minimum required value public int dfs(int []A, int state, int index) { // Base Case if (index >= k) { return 0; } // Stores the minimum value // of the current state int res = 1000; // If dp[state][index] is // already calculated if (dp[state,index] != -1) { // return dp[state][index] return dp[state,index]; } // Traverse over all the bits foreach(int bit in bits) { // If count of set bit is N/K if(Convert.ToString(bit, 2).Count(c => c == '1')== goal) { // Store the new state after // choosing N/K elements int newstate = state; // Stores the minimum and // maximum of current subset int mn = 100, mx = -1; // Stores if the elements // have been already // selected or not bool []visit = new bool[n + 1]; // Stores if it is possible // to select N/K elements bool good = true; // Traverse over the array for (int j = 0; j < n; j++) { // If not chosen already // for another subset if ((bit & (1 << j)) != 0) { // If already chosen // for another subset // or current subset if (visit[A[j]] == true || (state & (1 << j)) == 0) { // Mark the good false good = false; break; } // Mark the current // number visited visit[A[j]] = true; // Mark the current // position in mask // newstate newstate = newstate ^ (1 << j); // Update the maximum // and minimum mx = Math.Max(mx, A[j]); mn = Math.Min(mn, A[j]); } } // If good is true then // Update the res if (good) { res = Math.Min( res, mx - mn + dfs(A, newstate, index + 1)); } } } // Update the current sp state dp[state,index] = res; // Return the res return res; }}// Driver Codeclass GFG { public static void Main() { Solution st = new Solution(); int[] arr = { 1, 2, 1, 4 }; int K = 2; // Function Call Console.Write( st.minimumIncompatibility(arr, K)); }}// This code is contributed by rutvik_56. |
Javascript
<script>// Javascript program for the above approachlet k,n,goal;let dp;let bits = [];// Function to find the minimum// incompatibility sumfunction minimumIncompatibility(A,K){ n = A.length; k = K; goal = Math.floor(n / k); // Stores the count of element let map = new Map(); // Traverse the array for (let i=0;i< A.length;i++) { // If number i not occurs // in Map if (!map.has(A[i])) // Put the element // in the Map map.set(A[i], 0); // Increment the count of // i in the Hash Map map.set(A[i], map.get(A[i]) + 1); // If count of i in Map is // greater than K then // return -1 if (map.get(A[i]) > k) return -1; } // Stores all total state let state = (1 << n) - 1; // Traverse over all the state for (let i = 0; i <= state; i++) { // If number of set bit // is equal to N/K if (i.toString(2).split('0').join('').length == goal) bits.push(i); } // Stores the minimum value // at a state dp = new Array(1 << n); // Initialize the dp state // with -1 for (let i = 0; i < dp.length; i++) { dp[i]=new Array(k); for(let j=0;j<k;j++) dp[i][j]=-1; } // Call the recursive function return dfs(A, state, 0);}// Recursive function to find// the minimum required valuefunction dfs(A,state,index){ // Base Case if (index >= k) { return 0; } // Stores the minimum value // of the current state let res = 1000; // If dp[state][index] is // already calculated if (dp[state][index] != -1) { // return dp[state][index] return dp[state][index]; } // Traverse over all the bits for (let bit=0;bit< bits.length;bit++) { // If count of set bit is N/K if (bits[bit].toString(2).split('0').join('').length == goal) { // Store the new state after // choosing N/K elements let newstate = state; // Stores the minimum and // maximum of current subset let mn = 100, mx = -1; // Stores if the elements // have been already // selected or not let visit = new Array(n + 1); for(let i=0;i<=n;i++) { visit[i]=false; } // Stores if it is possible // to select N/K elements let good = true; // Traverse over the array for (let j = 0; j < n; j++) { // If not chosen already // for another subset if ((bits[bit] & (1 << j)) != 0) { // If already chosen // for another subset // or current subset if (visit[A[j]] == true || (state & (1 << j)) == 0) { // Mark the good false good = false; break; } // Mark the current // number visited visit[A[j]] = true; // Mark the current // position in mask // newstate newstate = newstate ^ (1 << j); // Update the maximum // and minimum mx = Math.max(mx, A[j]); mn = Math.min(mn, A[j]); } } // If good is true then // Update the res if (good) { res = Math.min( res, mx - mn + dfs(A, newstate, index + 1)); } } } // Update the current sp state dp[state][index] = res; // Return the res return res;}// Driver Codelet arr=[1, 2, 1, 4];let K = 2;document.write(minimumIncompatibility(arr, K))// This code is contributed by unknown2108</script> |
Output:
4
Time Complexity: O(N2*22*N)
Auxiliary Space: O(N)
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!
