Count pairs with set bits sum equal to K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  32 NEW_LINE unsigned int countSetBits ( int n ) { unsigned int count = 0 ; while ( n ) { n &= ( n - 1 ) ; count ++ ; } return count ; } int pairs ( int arr [ ] , int n , int k ) { int count = 0 ; int f [ MAX + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) f [ countSetBits ( arr [ i ] ) ] ++ ; for ( int i = 0 ; i <= MAX ; i ++ ) { for ( int j = i ; j <= MAX ; j ++ ) { if ( i + j == k ) { if ( i == j ) count += ( ( f [ i ] * ( f [ i ] - 1 ) ) / 2 ) ; else count += ( f [ i ] * f [ j ] ) ; } } } return count ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 4 ; cout << pairs ( arr , n , k ) ; return 0 ; }