Number of ordered pairs such that ( Ai & Aj ) = 0 | Java program to calculate the number of ordered pairs such that their bitwise and is zero ; Efficient function to count pairs ; Stores the frequency of each number ; Count the frequency of every element ; Iterate for al possible values that a [ i ] can be ; If the last bit is ON ; is the last bit is OFF ; Iterate till n ; If mask 's ith bit is set ; If mask 's ith bit is not set ; Iterate for all the array element and count the number of pairs ; return answer ; Driver code
import java . util . * ; class GFG { static int N = 15 ; public static int countPairs ( int a [ ] , int n ) { HashMap < Integer , Integer > hash = new HashMap < > ( ) ; int dp [ ] [ ] = new int [ 1 << N ] [ N + 1 ] ; for ( int i = 0 ; i < n ; ++ i ) { if ( hash . containsKey ( a [ i ] ) ) { hash . replace ( a [ i ] , hash . get ( a [ i ] ) + 1 ) ; } else { hash . put ( a [ i ] , 1 ) ; } } for ( int mask = 0 ; mask < ( 1 << N ) ; ++ mask ) { if ( ( mask & 1 ) != 0 ) { if ( hash . containsKey ( mask ) ) { dp [ mask ] [ 0 ] = hash . get ( mask ) ; } if ( hash . containsKey ( mask ^ 1 ) ) { dp [ mask ] [ 0 ] += hash . get ( mask ^ 1 ) ; } } else { if ( hash . containsKey ( mask ) ) { dp [ mask ] [ 0 ] = hash . get ( mask ) ; } } for ( int i = 1 ; i <= N ; ++ i ) { if ( ( mask & ( 1 << i ) ) != 0 ) { dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] + dp [ mask ^ ( 1 << i ) ] [ i - 1 ] ; } else { dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] ; } } } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans += dp [ ( ( 1 << N ) - 1 ) ^ a [ i ] ] [ N ] ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 5 , 4 , 1 , 6 } ; int n = a . length ; System . out . print ( countPairs ( a , n ) ) ; } }