Count all pairs of an array which differ in K bits | Below is C ++ approach of finding total k bit difference pairs ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long kBitDifferencePairs ( int arr [ ] , int n , int k ) { int MAX = * max_element ( arr , arr + n ) ; long long count [ MAX + 1 ] ; memset ( count , 0 , sizeof ( count ) ) ; for ( int i = 0 ; i < n ; ++ i ) ++ count [ arr [ i ] ] ; long long ans = 0 ; if ( k == 0 ) { for ( int i = 0 ; i <= MAX ; ++ i ) ans += ( count [ i ] * ( count [ i ] - 1 ) ) / 2 ; return ans ; } for ( int i = 0 ; i <= MAX ; ++ i ) { if ( ! count [ i ] ) continue ; for ( int j = i + 1 ; j <= MAX ; ++ j ) { if ( __builtin_popcount ( i ^ j ) == k ) ans += count [ i ] * count [ j ] ; } } return ans ; } int main ( ) { int k = 2 ; int arr [ ] = { 2 , 4 , 1 , 3 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Total ▁ pairs ▁ for ▁ k ▁ = ▁ " << k << " ▁ are ▁ = ▁ " << kBitDifferencePairs ( arr , n , k ) << " STRNEWLINE " ; k = 3 ; cout << " Total ▁ pairs ▁ for ▁ k ▁ = ▁ " << k << " ▁ are ▁ = ▁ " << kBitDifferencePairs ( arr , n , k ) ; return 0 ; }