Count of pairs in an Array with same number of set bits | Function to return the count of Pairs ; Get the maximum element ; Array to store count of bits of all elements upto maxm ; Store the set bits for powers of 2 ; Compute the set bits for the remaining elements ; Store the frequency of respective counts of set bits ; Driver Code
def countPairs ( arr , N ) : NEW_LINE INDENT maxm = max ( arr ) NEW_LINE i = 0 NEW_LINE k = 0 NEW_LINE bitscount = [ 0 for i in range ( maxm + 1 ) ] NEW_LINE i = 1 NEW_LINE while i <= maxm : NEW_LINE INDENT bitscount [ i ] = 1 NEW_LINE i *= 2 NEW_LINE DEDENT for i in range ( 1 , maxm + 1 ) : NEW_LINE INDENT if ( bitscount [ i ] == 1 ) : NEW_LINE INDENT k = i NEW_LINE DEDENT if ( bitscount [ i ] == 0 ) : NEW_LINE INDENT bitscount [ i ] = ( bitscount [ k ] + bitscount [ i - k ] ) NEW_LINE DEDENT DEDENT setbits = dict ( ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT if bitscount [ arr [ i ] ] in setbits : NEW_LINE INDENT setbits [ bitscount [ arr [ i ] ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT setbits [ bitscount [ arr [ i ] ] ] = 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for it in setbits . values ( ) : NEW_LINE INDENT ans += it * ( it - 1 ) // 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 12 NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ] NEW_LINE print ( countPairs ( arr , N ) ) NEW_LINE DEDENT