What does it solve?
Count all contiguous subarrays whose XOR equals K. Key: prefix XOR from 0..i is px[i]. Subarray (j,i] XORs to px[i] ⊕ px[j]. We need this to equal K.
The Trick
// We need: px[i] ⊕ px[j] = K
// So: px[j] = px[i] ⊕ K
need = prefixXOR ⊕ K
count += map[need]
map[prefixXOR]++
// So: px[j] = px[i] ⊕ K
need = prefixXOR ⊕ K
count += map[need]
map[prefixXOR]++
Interactive Visualization
Current
Prefix XOR
Match Found
Array (prefix XOR shown below)
Hash Map (prefix XOR → count)
{0: 1}
Step 0 of 0
Prefix XOR
0
Need (px⊕K)
—
Found in Map
0
Total Count
0
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Subarray XOR = K
int countSubarraysXOR(vector<int>& arr, int K) { unordered_map<int, int> mp; mp[0] = 1; // empty prefix int px = 0, count = 0; for (int val : arr) { px ^= val; // running prefix XOR int need = px ^ K; // what prefix would make subarray XOR = K count += mp[need]; // add all matching prefixes mp[px]++; // record current prefix } return count; }
Complexity
Time
O(N)
Single pass with hash map lookups.
Space
O(N)
Hash map stores at most N prefix XOR values.