Partition an array into two subsets with equal count of unique elements | Java program for the above approach ; Function to partition the array into two subsets such that count of unique elements in both subsets is the same ; Stores the subset number for each array elements ; Stores the count of unique array elements ; Stores the frequency of elements ; Traverse the array ; Count of elements having a frequency of 1 ; Check if there exists any element with frequency > 2 ; Count of elements needed to have frequency exactly 1 in each subset ; Initialize all values in the / array ans [ ] as 1 ; Traverse the array ans [ ] ; This array element is a part of first subset ; Half array elements with frequency 1 are part of the second subset ; If count of elements is exactly 1 are odd and has no element with frequency > 2 ; If count of elements that occurs exactly once are even ; Print the result ; If the count of elements has exactly 1 frequency are odd and there is an element with frequency greater than 2 ; Print the result ; Driver Codea
import java . util . HashMap ; class GFG { public static void arrayPartition ( int a [ ] , int n ) { int [ ] ans = new int [ n ] ; int cnt = 0 ; int ind = 0 , flag = 0 ; HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . containsKey ( a [ i ] ) ) { mp . put ( a [ i ] , mp . get ( a [ i ] ) + 1 ) ; } else { mp . put ( a [ i ] , 1 ) ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( mp . get ( a [ i ] ) == 1 ) cnt ++ ; if ( mp . get ( a [ i ] ) > 2 && flag == 0 ) { flag = 1 ; ind = i ; } } int p = ( cnt + 1 ) / 2 ; int ans1 = 0 ; for ( int i = 0 ; i < n ; i ++ ) ans [ i ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . get ( a [ i ] ) == 1 && ans1 < p ) { ans [ i ] = 1 ; ans1 ++ ; } else if ( mp . get ( a [ i ] ) == 1 ) { ans [ i ] = 2 ; } } if ( cnt % 2 == 1 && flag == 0 ) { System . out . println ( - 1 + "NEW_LINE"); return ; } if ( cnt % 2 == 0 ) { for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( ans [ i ] + " ▁ " ) ; } } else { for ( int i = 0 ; i < n ; i ++ ) { if ( ind == i ) System . out . print ( 2 + " ▁ " ) ; else System . out . print ( ans [ i ] + " ▁ " ) ; } } } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 1 , 2 , 3 , 4 , 4 } ; int N = arr . length ; arrayPartition ( arr , N ) ; } }