Minimize sum of incompatibilities of K equal | Java program for the above approach ; Function to find the minimum incompatibility sum ; Stores the count of element ; Traverse the array ; If number i not occurs in Map ; Put the element in the Map ; Increment the count of i in the Hash Map ; If count of i in Map is greater than K then return - 1 ; Stores all total state ; Traverse over all the state ; If number of set bit is equal to N / K ; Stores the minimum value at a state ; Initialize the dp state with - 1 ; Call the recursive function ; Recursive function to find the minimum required value ; Base Case ; Stores the minimum value of the current state ; If dp [ state ] [ index ] is already calculated ; return dp [ state ] [ index ] ; Traverse over all the bits ; If count of set bit is N / K ; Store the new state after choosing N / K elements ; Stores the minimum and maximum of current subset ; Stores if the elements have been already selected or not ; Stores if it is possible to select N / K elements ; Traverse over the array ; If not chosen already for another subset ; If already chosen for another subset or current subset ; Mark the good false ; Mark the current number visited ; Mark the current position in mask newstate ; Update the maximum and minimum ; If good is true then Update the res ; Update the current sp state ; Return the res ; Driver Code ; Function Call
import java . io . * ; import java . util . * ; class Solution { int k ; int n ; int goal ; int dp [ ] [ ] ; List < Integer > bits = new ArrayList < > ( ) ; public int minimumIncompatibility ( int [ ] A , int k ) { this . n = A . length ; this . k = k ; goal = n / k ; Map < Integer , Integer > map = new HashMap < > ( ) ; for ( int i : A ) { if ( ! map . containsKey ( i ) ) map . put ( i , 0 ) ; map . put ( i , map . get ( i ) + 1 ) ; if ( map . get ( i ) > k ) return - 1 ; } int state = ( 1 << n ) - 1 ; for ( int i = 0 ; i <= state ; i ++ ) { if ( Integer . bitCount ( i ) == goal ) bits . add ( i ) ; } dp = new int [ 1 << n ] [ k ] ; for ( int i = 0 ; i < dp . length ; i ++ ) { Arrays . fill ( dp [ i ] , - 1 ) ; } return dfs ( A , state , 0 ) ; } public int dfs ( int A [ ] , int state , int index ) { if ( index >= k ) { return 0 ; } int res = 1000 ; if ( dp [ state ] [ index ] != - 1 ) { return dp [ state ] [ index ] ; } for ( int bit : bits ) { if ( Integer . bitCount ( bit ) == goal ) { int newstate = state ; int mn = 100 , mx = - 1 ; boolean visit [ ] = new boolean [ n + 1 ] ; boolean good = true ; for ( int j = 0 ; j < n ; j ++ ) { if ( ( bit & ( 1 << j ) ) != 0 ) { if ( visit [ A [ j ] ] == true || ( state & ( 1 << j ) ) == 0 ) { good = false ; break ; } visit [ A [ j ] ] = true ; newstate = newstate ^ ( 1 << j ) ; mx = Math . max ( mx , A [ j ] ) ; mn = Math . min ( mn , A [ j ] ) ; } } if ( good ) { res = Math . min ( res , mx - mn + dfs ( A , newstate , index + 1 ) ) ; } } } dp [ state ] [ index ] = res ; return res ; } } class GFG { public static void main ( String [ ] args ) { Solution st = new Solution ( ) ; int [ ] arr = { 1 , 2 , 1 , 4 } ; int K = 2 ; System . out . print ( st . minimumIncompatibility ( arr , K ) ) ; } }