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
using System ; using System . Collections ; using System . Collections . Generic ; using System . Text ; class GFG { static int countPairs ( int [ ] arr , int N ) { int maxm = - int . MaxValue ; for ( int j = 0 ; j < N ; j ++ ) { if ( maxm < arr [ j ] ) { maxm = arr [ j ] ; } } int i , k = 0 ; int [ ] bitscount = new int [ maxm + 1 ] ; Array . Fill ( bitscount , 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 ] ; } } Dictionary < int , int > setbits = new Dictionary < int , int > ( ) ; for ( int j = 0 ; j < N ; j ++ ) { if ( setbits . ContainsKey ( bitscount [ arr [ j ] ] ) ) { setbits [ bitscount [ arr [ j ] ] ] ++ ; } else { setbits [ bitscount [ arr [ j ] ] ] = 1 ; } } int ans = 0 ; foreach ( KeyValuePair < int , int > it in setbits ) { ans += it . Value * ( it . Value - 1 ) / 2 ; } return ans ; } public static void Main ( string [ ] args ) { int N = 12 ; int [ ] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 } ; Console . Write ( countPairs ( arr , N ) ) ; } }