Partition an array into two subsets with equal count of unique elements | 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
def arrayPartition ( a , n ) : NEW_LINE INDENT ans = [ 0 ] * n NEW_LINE cnt = 0 NEW_LINE ind , flag = 0 , 0 NEW_LINE mp = { } NEW_LINE for i in a : NEW_LINE INDENT mp [ i ] = mp . get ( i , 0 ) + 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( ( a [ i ] in mp ) and mp [ a [ i ] ] == 1 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT if ( mp [ a [ i ] ] > 2 and flag == 0 ) : NEW_LINE INDENT flag = 1 NEW_LINE ind = i NEW_LINE DEDENT DEDENT p = ( cnt + 1 ) // 2 NEW_LINE ans1 = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans [ i ] = 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( ( a [ i ] in mp ) and mp [ a [ i ] ] == 1 and ans1 < p ) : NEW_LINE INDENT ans [ i ] = 1 NEW_LINE ans1 += 1 NEW_LINE DEDENT elif ( ( a [ i ] in mp ) and mp [ a [ i ] ] == 1 ) : NEW_LINE INDENT ans [ i ] = 2 NEW_LINE DEDENT DEDENT if ( cnt % 2 == 1 and flag == 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT if ( cnt % 2 == 0 ) : NEW_LINE INDENT print ( * ans ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if ( ind == i ) : NEW_LINE INDENT print ( 2 , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 2 , 3 , 4 , 4 ] NEW_LINE N = len ( arr ) NEW_LINE arrayPartition ( arr , N ) NEW_LINE DEDENT