Count number of subsets having a particular XOR value | Python 3 arr dynamic programming solution to finding the number of subsets having xor of their elements as k ; Returns count of subsets of arr [ ] with XOR value equals to k . ; Find maximum element in arr [ ] ; Maximum possible XOR value ; Initializing all the values of dp [ i ] [ j ] as 0 ; The xor of empty subset is 0 ; Fill the dp table ; The answer is the number of subset from set arr [ 0. . n - 1 ] having XOR of elements as k ; Driver Code
import math 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 ) ( math . log2 ( max_ele ) + 1 ) ) - 1 NEW_LINE if ( k > m ) : NEW_LINE return 0 NEW_LINE dp = [ [ 0 for i in range ( m + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j ^ arr [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT return dp [ n ] [ k ] NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE k = 4 NEW_LINE n = len ( arr ) NEW_LINE print ( " Count ▁ of ▁ subsets ▁ is " , subsetXOR ( arr , n , k ) ) NEW_LINE