Number of subsets with same AND , OR and XOR values in an Array | Python3 program to find the number of subsets with equal bitwise AND , OR and XOR values ; Function to find the number of subsets with equal bitwise AND , OR and XOR values ; Precompute the modded powers of two for subset counting ; Loop to iterate and find the modded powers of two for subset counting ; Map to store the frequency of each element ; Loop to compute the frequency ; For every element > 0 , the number of subsets formed using this element only is equal to 2 ^ ( frequency [ element ] - 1 ) . And for 0 , we have to find all the subsets , so 2 ^ ( frequency [ element ] ) - 1 ; If element is greater than 0 ; Driver code
mod = 1000000007 NEW_LINE def countSubsets ( a , n ) : NEW_LINE INDENT answer = 0 NEW_LINE powerOfTwo = [ 0 for x in range ( 100005 ) ] NEW_LINE powerOfTwo [ 0 ] = 1 NEW_LINE for i in range ( 1 , 100005 ) : NEW_LINE INDENT powerOfTwo [ i ] = ( powerOfTwo [ i - 1 ] * 2 ) % mod NEW_LINE DEDENT frequency = { } NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if a [ i ] in frequency : NEW_LINE INDENT frequency [ a [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT frequency [ a [ i ] ] = 1 NEW_LINE DEDENT DEDENT for key , value in frequency . items ( ) : NEW_LINE INDENT if ( key != 0 ) : NEW_LINE INDENT answer = ( answer % mod + powerOfTwo [ value - 1 ] ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT answer = ( answer % mod + powerOfTwo [ value ] - 1 + mod ) % mod NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT N = 6 NEW_LINE A = [ 1 , 3 , 2 , 1 , 2 , 1 ] NEW_LINE print ( countSubsets ( A , N ) ) NEW_LINE