Partition an array into two subsets with equal count of unique elements | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void arrayPartition ( int a [ ] , int n ) { int ans [ n ] ; int cnt = 0 ; int ind , flag = 0 ; map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) { mp [ a [ i ] ] ++ ; } for ( int i = 0 ; i < n ; i ++ ) { if ( mp [ a [ i ] ] == 1 ) cnt ++ ; if ( mp [ 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 [ a [ i ] ] == 1 && ans1 < p ) { ans [ i ] = 1 ; ans1 ++ ; } else if ( mp [ a [ i ] ] == 1 ) { ans [ i ] = 2 ; } } if ( cnt % 2 == 1 && flag == 0 ) { cout << -1 << endl ; return ; } if ( cnt % 2 == 0 ) { for ( int i = 0 ; i < n ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } else { for ( int i = 0 ; i < n ; i ++ ) { if ( ind == i ) cout << 2 << " ▁ " ; else cout << ans [ i ] << " ▁ " ; } } } int main ( ) { int arr [ ] = { 1 , 1 , 2 , 3 , 4 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; arrayPartition ( arr , N ) ; return 0 ; }