Count no . of ordered subsets having a particular XOR value | Python 3 implementation of the approach ; Returns count of ordered subsets of arr [ ] with XOR value = K ; Find maximum element in arr [ ] ; Maximum possible XOR value ; The value of dp [ i ] [ j ] [ k ] is the number of subsets of length k having XOR of their elements as j from the set arr [ 0. . . i - 1 ] ; Initializing all the values of dp [ i ] [ j ] [ k ] as 0 ; The xor of empty subset is 0 ; Fill the dp table ; The answer is the number of subsets of all lengths from set arr [ 0. . n - 1 ] having XOR of elements as k ; Driver Code
from math import log2 NEW_LINE def subsetXOR ( arr , n , K ) : NEW_LINE INDENT max_ele = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( arr [ i ] > max_ele ) : NEW_LINE INDENT max_ele = arr [ i ] NEW_LINE DEDENT DEDENT m = ( 1 << int ( log2 ( max_ele ) + 1 ) ) - 1 NEW_LINE dp = [ [ [ 0 for i in range ( n + 1 ) ] for j in range ( m + 1 ) ] for k in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT for k in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT for k in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = dp [ i - 1 ] [ j ] [ k ] NEW_LINE if ( k != 0 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] += k * dp [ i - 1 ] [ j ^ arr [ i - 1 ] ] [ k - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans += dp [ n ] [ K ] [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 ] NEW_LINE k = 1 NEW_LINE n = len ( arr ) NEW_LINE print ( subsetXOR ( arr , n , k ) ) NEW_LINE DEDENT