Count Subarrays With XOR K
WHAT IT SAYS
Count the contiguous subarrays whose elements XOR together to exactly k.
WHAT IT'S REALLY ASKING
"XOR is its own undo. So if the running XOR up to here is X, a subarray ending here equals k exactly when the prefix you chop off the front is X ^ k. The only question left is: how many times have you already passed through that value?"
XOR every subarray
O(n^2) time, O(1) spaceFix a start, extend an end, carry a running XOR, and count the times it equals k. Reset for each new start.
WHERE THE WORK IS WASTED — The array has exactly n+1 prefix-XOR values in it, and brute force reconstructs all of them from scratch for every starting index. Worse, at each right end you are re-answering a question you have implicitly answered before — 'did any earlier prefix have value X ^ k?' — by walking the past again, when the past could have been tallied once, on the way through.
XOR undoes itself, so a range is two prefixes XORed.
Let P[i] be the XOR of the first i elements. Then P[i] ^ P[j+1] = xor(i..j), because every element before index i appears in BOTH prefixes, and anything XORed with itself is 0. The shared history cancels out. XOR is not just associative — it is its own inverse, which is exactly the property that lets a prefix be subtracted. Now demand xor(i..j) = k, so P[i] ^ P[j+1] = k. XOR both sides by P[j+1] and the left side collapses: P[i] = P[j+1] ^ k. No division, no signs, no overflow — the inverse operation is the operation itself. Read the consequence. With the right end fixed at j, a valid start is not something to search for; it is any earlier position whose prefix-XOR equals one specific number. Counting subarrays becomes counting sightings of a value. That is a frequency lookup, O(1). It must be a frequency, not a flag. If three earlier prefixes all carried the value P[j+1] ^ k, then three different subarrays end at j, and each has a distinct start. A boolean 'have I seen it' would find one and silently lose the other two. And seed the tally with the value 0 appearing once — the empty prefix, before the array starts, really does XOR to 0. Skip that seeding and every subarray beginning at index 0 disappears from the count.
One pass, one tally
O(n) time, O(n) spaceCarry a running XOR, and a map from XOR value to how many times you have seen it, seeded with 0 -> 1. At each element: fold it into the running XOR, add map[running ^ k] to the answer, then bump map[running]. That is the whole algorithm; the algebra did the work.
Invertible Prefix
YOU'LL SEE IT AGAIN WHEN
- The range operator has an inverse (add/subtract, xor/xor), so a range value can be written as prefix-at-end combined with prefix-at-start.
- You are counting how many ranges qualify, so you need the frequency of past prefix states, not merely their existence.
- The operator does not care where inside the range something happened — only the endpoints matter, which rules out order-sensitive quantities like the position of the max.