Count of pairs in an Array with same number of set bits | Java 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
import java . util . * ; import java . lang . * ; class GFG { static int countPairs ( int [ ] arr , int N ) { int maxm = arr [ 0 ] ; for ( int j = 1 ; j < N ; j ++ ) { if ( maxm < arr [ j ] ) { maxm = arr [ j ] ; } } int i , k = 0 ; int [ ] bitscount = new int [ maxm + 1 ] ; Arrays . 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 ] ; } } Map < Integer , Integer > setbits = new HashMap < > ( ) ; for ( int j = 0 ; j < N ; j ++ ) { setbits . put ( bitscount [ arr [ j ] ] , setbits . getOrDefault ( bitscount [ arr [ j ] ] , 0 ) + 1 ) ; } int ans = 0 ; for ( int it : setbits . values ( ) ) { ans += it * ( it - 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 } ; System . out . println ( countPairs ( arr , N ) ) ; } }