Number of ordered pairs such that ( Ai & Aj ) = 0 | Python 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 ; initialize 0 to all ; 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
N = 15 NEW_LINE def countPairs ( a , n ) : NEW_LINE INDENT Hash = { } NEW_LINE dp = [ [ 0 for i in range ( N + 1 ) ] for j in range ( 1 << N ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if a [ i ] not in Hash : NEW_LINE INDENT Hash [ a [ i ] ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT Hash [ a [ i ] ] += 1 NEW_LINE DEDENT DEDENT mask = 0 NEW_LINE while ( mask < ( 1 << N ) ) : NEW_LINE INDENT if mask not in Hash : NEW_LINE INDENT Hash [ mask ] = 0 NEW_LINE DEDENT if ( mask & 1 ) : NEW_LINE INDENT dp [ mask ] [ 0 ] = Hash [ mask ] + Hash [ mask ^ 1 ] NEW_LINE dp [ mask ] [ 0 ] = Hash [ mask ] NEW_LINE DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( mask & ( 1 << i ) ) : NEW_LINE INDENT dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] + dp [ mask ^ ( 1 << i ) ] [ i - 1 ] NEW_LINE dp [ mask ] [ i ] = dp [ mask ] [ i - 1 ] NEW_LINE DEDENT DEDENT mask += 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans += dp [ ( ( 1 << N ) - 1 ) ^ a [ i ] ] [ N ] NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 5 , 4 , 1 , 6 ] NEW_LINE n = len ( a ) NEW_LINE print ( countPairs ( a , n ) ) NEW_LINE