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
function kBitDifferencePairs ( arr , n , k ) { let MAX = Math . max ( ... arr ) ; let count = new Array ( MAX + 1 ) . fill ( 0 ) ; for ( let i = 0 ; i < n ; ++ i ) ++ count [ arr [ i ] ] ; let ans = 0 ; if ( k == 0 ) { for ( let i = 0 ; i <= MAX ; ++ i ) ans += parseInt ( ( count [ i ] * ( count [ i ] - 1 ) ) / 2 ) ; return ans ; } for ( let i = 0 ; i <= MAX ; ++ i ) { if ( ! count [ i ] ) continue ; for ( let j = i + 1 ; j <= MAX ; ++ j ) { if ( BitCount ( i ^ j ) == k ) ans += count [ i ] * count [ j ] ; } } return ans ; } function BitCount ( n ) { let count = 0 ; while ( n > 0 ) { count += n & 1 ; n >>= 1 ; } return count ; } let k = 2 ; let arr = [ 2 , 4 , 1 , 3 , 1 ] ; let n = arr . length ; document . write ( " " + k + " " + kBitDifferencePairs ( arr , n , k ) + " " ) ; k = 3 ; document . write ( " " + k + " " + kBitDifferencePairs ( arr , n , k ) + " " ) ;