Number of ordered pairs such that ( Ai & Aj ) = 0 | CPP 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 ; else is the last bit is OFF ; iterate till n ; if mask 's ith bit is set ; else if mask 's ith bit is not set ; iterate for all the array element and count the number of pairs ; return answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 15 ; long long countPairs ( int a [ ] , int n ) { unordered_map < int , int > hash ; long long dp [ 1 << N ] [ N + 1 ] ; for ( int i = 0 ; i < n ; ++ i ) hash [ a [ i ] ] += 1 ; for ( long long mask = 0 ; mask < ( 1 << N ) ; ++ mask ) { if ( mask & 1 ) dp [ mask ] [ 0 ] = hash [ mask ] + hash [ mask ^ 1 ] ; dp [ mask ] [ 0 ] = hash [ mask ] ; for ( int i = 1 ; i <= N ; ++ i ) { if ( mask & ( 1 << i ) ) { dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] + dp [ mask ^ ( 1 << i ) ] [ i - 1 ] ; } dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] ; } } long long ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) ans += dp [ ( ( 1 << N ) - 1 ) ^ a [ i ] ] [ N ] ; return ans ; } int main ( ) { int a [ ] = { 5 , 4 , 1 , 6 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << countPairs ( a , n ) ; return 0 ; }