Pattern visualizer
Subarray with Given XOR
XOR undoes itself: any value XORed in twice vanishes. That single fact turns this into a counting problem. Let prefix(i) be the XOR of A[0..i]; then the XOR of A[l..r] is prefix(r) XOR prefix(l-1), because the front part A[0..l-1] sits inside both prefixes and cancels. So a subarray ending at r has XOR B exactly when some earlier prefix equals prefix(r) XOR B. Walk left to right keeping a map from prefix value to how many times it has occurred, and each index contributes its matching count in constant time. Seeding the map with prefix 0 is what allows a subarray to start at index 0 — that seed is the step most implementations get wrong. Animated on: A = [4,2,2,6,4,6,2], B = 6 — count the subarrays whose XOR is exactly B..
Prefix XOR plus a map of what has been seen
A subarray A[l..r] has XOR 6 exactly when prefix(r) XOR prefix(l-1) = 6, because the shared front part A[0..l-1] appears in both prefixes and XOR cancels anything repeated. So instead of trying every pair of endpoints, walk once and ask each r: which earlier prefix would make this work? The empty prefix 0 is recorded up front — without it, a subarray that starts at index 0 could never be counted.
1FUNCTION countSubarraysWithXor(A, B)2 count <- 03 prefix <- 04 seen <- EMPTY MAP5 seen[0] <- 16 FOR r <- 0 TO LENGTH(A) - 17 prefix <- prefix XOR A[r]8 need <- prefix XOR B9 IF need IN seen10 count <- count + seen[need]11 seen[prefix] <- seen[prefix] + 112 RETURN count
← / → step · space play · Home restart