Subarray XOR with Target
MediumPractice library · +20 XPbit manipulationhash mapprefix sum
Given an array A of N integers and a target integer K, find the number of subarrays whose elements have a bitwise XOR sum equal to K. A subarray is a contiguous non-empty sequence of elements within an array.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers A_1, A_2, ..., A_N, separated by spaces.
Output
Print a single integer: the count of subarrays whose XOR sum is K.
Constraints
1 <= N <= 200000 0 <= A_i <= 10^9 0 <= K <= 10^9 Time limit: 1000 ms
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
4 3 1 2 3 4
Output
2
Subarrays are [1,2] (1^2=3), [3] (3), [1,2,3,4] (1^2^3^4=4).
Example 2
Input
3 0 1 1 1
Output
2
Subarrays are [1,1] (1^1=0), [1,1] (1^1=0).
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
4 3 1 2 3 4
Example 2 input
3 0 1 1 1