Count of pairs in an Array with same number of set bits | C ++ Program to count possible number of pairs of elements with same number of set bits . ; Function to return the count of Pairs ; Get the maximum element ; Array to store count of bits of all elements upto maxm ; Store the set bits for powers of 2 ; Compute the set bits for the remaining elements ; Store the frequency of respective counts of set bits ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairs ( int arr [ ] , int N ) { int maxm = * max_element ( arr , arr + N ) ; int i , k ; int bitscount [ maxm + 1 ] = { 0 } ; for ( i = 1 ; i <= maxm ; i *= 2 ) bitscount [ i ] = 1 ; for ( i = 1 ; i <= maxm ; i ++ ) { if ( bitscount [ i ] == 1 ) k = i ; if ( bitscount [ i ] == 0 ) { bitscount [ i ] = bitscount [ k ] + bitscount [ i - k ] ; } } map < int , int > setbits ; for ( int i = 0 ; i < N ; i ++ ) { setbits [ bitscount [ arr [ i ] ] ] ++ ; } int ans = 0 ; for ( auto it : setbits ) { ans += it . second * ( it . second - 1 ) / 2 ; } return ans ; } int main ( ) { int N = 12 ; int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 } ; cout << countPairs ( arr , N ) ; return 0 ; }