Count Subarrays With a Given XOR
You are given an array of non-negative integers nums and a non-negative integer k.
A subarray is a part of the array made of neighbouring elements, with at least one element.
The XOR of a subarray is all of its elements combined with the bitwise XOR operator (^).
Return the number of subarrays whose XOR is exactly k.
Let p be the XOR of the first few elements (a prefix). The XOR of a subarray is the XOR of two prefixes. So for each prefix p, count how many earlier prefixes are equal to p ^ k. Remember the empty prefix, whose XOR is 0.
Examples
Example 1
- Input:
- [5,1,4,3,7], 5
- Output:
- 2
The subarray [5] has XOR 5, and the subarray [1, 4] has XOR 1 ^ 4 = 5. No other subarray has XOR 5.
Example 2
- Input:
- [0,0,0], 0
- Output:
- 6
Every subarray contains only zeros, so every one has XOR 0. There are 3 + 2 + 1 = 6 subarrays.
Example 3
- Input:
- [2,6], 1
- Output:
- 0
The subarrays have XOR 2, 6 and 2 ^ 6 = 4. None of them is 1.
Constraints
1 <= nums.length <= 200 <= nums[i] <= 150 <= k <= 15
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.