Count all pairs of an array which differ in K bits | Function to calculate K bit different pairs in array ; Get the maximum value among all array elemensts ; Set the count array to 0 , count [ ] stores the total frequency of array elements ; Initialize result ; For 0 bit answer will be total count of same number ; if count [ i ] is 0 , skip the next loop as it will not contribute the answer ; Update answer if k differ bit found ; Driver code
def kBitDifferencePairs ( arr , n , k ) : NEW_LINE INDENT MAX = max ( arr ) NEW_LINE count = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE if ( k == 0 ) : NEW_LINE INDENT for i in range ( MAX + 1 ) : NEW_LINE INDENT ans += ( count [ i ] * ( count [ i ] - 1 ) ) // 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT for i in range ( MAX + 1 ) : NEW_LINE INDENT if ( count [ i ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( i + 1 , MAX + 1 ) : NEW_LINE INDENT if ( bin ( i ^ j ) . count ( '1' ) == k ) : NEW_LINE INDENT ans += count [ i ] * count [ j ] NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT k = 2 NEW_LINE arr = [ 2 , 4 , 1 , 3 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Total ▁ pairs ▁ for ▁ k ▁ = " , k , " are " , kBitDifferencePairs ( arr , n , k ) ) NEW_LINE k = 3 NEW_LINE print ( " Total ▁ pairs ▁ for ▁ k ▁ = " , k , " are " , kBitDifferencePairs ( arr , n , k ) ) NEW_LINE