Number of ordered pairs such that ( Ai & Aj ) = 0 | C # 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
using System ; using System . Collections . Generic ; class GFG { static int N = 15 ; static int countPairs ( int [ ] a , int n ) { Dictionary < int , int > hash = new Dictionary < int , int > ( ) ; int [ , ] dp = new int [ 1 << N , N + 1 ] ; for ( int i = 0 ; i < n ; ++ i ) { if ( hash . ContainsKey ( a [ i ] ) ) { hash [ a [ i ] ] += 1 ; } else { hash . Add ( a [ i ] , 1 ) ; } } for ( int mask = 0 ; mask < ( 1 << N ) ; ++ mask ) { if ( ( mask & 1 ) != 0 ) { if ( hash . ContainsKey ( mask ) ) { dp [ mask , 0 ] = hash [ mask ] ; } if ( hash . ContainsKey ( mask ^ 1 ) ) { dp [ mask , 0 ] += hash [ mask ^ 1 ] ; } } else { if ( hash . ContainsKey ( mask ) ) { dp [ mask , 0 ] = hash [ 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 ; } static void Main ( ) { int [ ] a = { 5 , 4 , 1 , 6 } ; int n = a . Length ; Console . WriteLine ( countPairs ( a , n ) ) ; } }