You are given an array of n non-negative integers and a target value k. Consider every one of the 2^n subsets of the array (the empty subset is included and its XOR is defined as 0). Count how many subsets have a bitwise XOR of their elements exactly equal to k.
The answer is a single well-defined count, so it is unique. Note that the count can be as large as 2^n, so use a 64-bit-capable integer type.
A key fact: over GF(2), if the array's values span a linear space of rank r, then either no subset reaches k (answer 0), or exactly 2^(n - r) subsets do. You are encouraged to build a linear basis rather than enumerate all subsets, though for the given constraints enumeration would also fit in time.
Line 1: two space-separated integers n and k.
Line 2: n space-separated non-negative integers (this line is present but blank when n = 0).
A single integer: the number of subsets whose XOR equals k.
Example 1
Input
3 3 1 2 3
Expected
2
Explanation
Among the 8 subsets, exactly two XOR to 3: {3} and {1,2} (1 XOR 2 = 3). So the count is 2.
Example 2
Input
4 0 1 1 2 2
Expected
4
Explanation
The values 1 and 2 give rank 2, so 2^(4-2) = 4 subsets XOR to 0: the empty set, {1,1}, {2,2}, and {1,1,2,2}.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →