Count Subarrays with XOR K
Count the subarrays whose elements XOR to exactly k.
Intuition
XOR has the same prefix trick as sums, because XOR is its own inverse: xor(i..j) = pre[j] ⊕ pre[i−1]. A subarray XORs to k exactly when the current prefix XOR equals some earlier prefix ⊕ k. Count how many earlier prefixes equal pre ⊕ k.
Prefix sums, but with XOR. The enabling identity is that XOR is its own inverse: if the prefix up to j is pre and you want a segment equal to k, the prefix you need earlier is pre ^ k. That turns "count subarrays with property P" into "count how many earlier prefixes I've seen" — exactly the subarray-sum-equals-k technique with ^ swapping in for -.
Approach
Prefix XOR replaces prefix sum
Keep running pre = a[0]^…^a[i]. Subarray (j..i] has XOR pre ⊕ pre_j. We want that to equal k, i.e. pre_j == pre ⊕ k.
Count occurrences, don't just remember one
Unlike the longest variant, every earlier matching prefix gives a distinct subarray — so the map stores value → count and we add the whole count.
Seed with {0: 1}
The empty prefix has XOR 0, letting subarrays that start at index 0 be counted.
Solution & live demo
Common pitfalls
Omitting the {0: 1} seed
count = {}count = {0: 1}A subarray starting at index 0 needs an empty prefix to subtract against. Without the seed, every such subarray — including the whole array when it XORs to k — goes uncounted.
Recording the prefix before counting
pre ^= n count[pre] = count.get(pre, 0) + 1 ans += count.get(pre ^ k, 0)
pre ^= n ans += count.get(pre ^ k, 0) count[pre] = count.get(pre, 0) + 1
When k is 0, pre ^ k equals pre, so registering first lets the current prefix match itself and counts an empty subarray. Count against history, then join the history.
Searching for pre ^ k the wrong way round
ans += count.get(k ^ pre ^ pre, 0)
ans += count.get(pre ^ k, 0)
The needed earlier prefix comes straight from prefix_j ^ prefix_i = k, which rearranges to prefix_i = prefix_j ^ k. Because XOR is self-inverse, the rearrangement needs no sign flip — but it does need exactly these two operands.
Edge cases
Counts subarrays whose prefix XOR repeats — handled naturally by the same formula.
Counter accumulates; each earlier occurrence is a separate subarray.