Minimize sum of incompatibilities of K equal | Javascript 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
let k , n , goal ; let dp ; let bits = [ ] ; function minimumIncompatibility ( A , K ) { n = A . length ; k = K ; goal = Math . floor ( n / k ) ; let map = new Map ( ) ; for ( let i = 0 ; i < A . length ; i ++ ) { if ( ! map . has ( A [ i ] ) ) map . set ( A [ i ] , 0 ) ; map . set ( A [ i ] , map . get ( A [ i ] ) + 1 ) ; if ( map . get ( A [ i ] ) > k ) return - 1 ; } let state = ( 1 << n ) - 1 ; for ( let i = 0 ; i <= state ; i ++ ) { if ( i . toString ( 2 ) . split ( ' ' ) . join ( ' ' ) . length == goal ) bits . push ( i ) ; } dp = new Array ( 1 << n ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( k ) ; for ( let j = 0 ; j < k ; j ++ ) dp [ i ] [ j ] = - 1 ; } return dfs ( A , state , 0 ) ; } function dfs ( A , state , index ) { if ( index >= k ) { return 0 ; } let res = 1000 ; if ( dp [ state ] [ index ] != - 1 ) { return dp [ state ] [ index ] ; } for ( let bit = 0 ; bit < bits . length ; bit ++ ) { if ( bits [ bit ] . toString ( 2 ) . split ( ' ' ) . join ( ' ' ) . length == goal ) { let newstate = state ; let mn = 100 , mx = - 1 ; let visit = new Array ( n + 1 ) ; for ( let i = 0 ; i <= n ; i ++ ) { visit [ i ] = false ; } let good = true ; for ( let j = 0 ; j < n ; j ++ ) { if ( ( bits [ 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 ; } let arr = [ 1 , 2 , 1 , 4 ] ; let K = 2 ; document . write ( minimumIncompatibility ( arr , K ) )