Count pairs with set bits sum equal to K | Python implementation of the approach ; Function to return the count of set bits in n ; Function to return the count of required pairs ; To store the count ; Frequency array ; If current pair satisfies the given condition ; ( arr [ i ] , arr [ i ] ) cannot be a valid pair ; Driver code
MAX = 32 NEW_LINE def countSetBits ( n ) : NEW_LINE INDENT count = 0 ; NEW_LINE while ( n ) : NEW_LINE INDENT n &= ( n - 1 ) ; NEW_LINE count += 1 ; NEW_LINE DEDENT return count ; NEW_LINE DEDENT def pairs ( arr , n , k ) : NEW_LINE INDENT count = 0 ; NEW_LINE f = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT f [ countSetBits ( arr [ i ] ) ] += 1 ; NEW_LINE DEDENT for i in range ( MAX + 1 ) : NEW_LINE INDENT for j in range ( 1 , MAX + 1 ) : NEW_LINE INDENT if ( i + j == k ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT count += ( ( f [ i ] * ( f [ i ] - 1 ) ) / 2 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT count += ( f [ i ] * f [ j ] ) ; NEW_LINE DEDENT DEDENT DEDENT DEDENT return count ; NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE k = 4 NEW_LINE print ( pairs ( arr , n , k ) ) NEW_LINE