Count Subarrays with given XOR

Prefix XOR plus a map of what has been seen

time O(n)space O(n)

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.

Details

Animated on: A = [4,2,2,6,4,6,2], B = 6 — count the subarrays whose XOR is exactly B.

Problem:Count Subarrays with given XORMedium

Prefix XOR plus a map of what has been seen

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

[6]

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.

Pseudocode

1FUNCTION countSubarraysWithXor(A, B)
2  count <- 0
3  prefix <- 0
4  seen <- EMPTY MAP
5  seen[0] <- 1
6  FOR r <- 0 TO LENGTH(A) - 1
7    prefix <- prefix XOR A[r]
8    need <- prefix XOR B
9    IF need IN seen
10      count <- count + seen[need]
11    seen[prefix] <- seen[prefix] + 1
12  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 9 steps

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.
Prefix through index 0 is 4, so the partner it needs is 4 XOR 6 = 2. No earlier prefix ever equalled 2, so nothing ending at index 0 can carry XOR 6 — the count stays 0. Prefix 4 is filed away anyway, since a later index may need it as its own partner.
Prefix through index 1 is 6, so the partner it needs is 6 XOR 6 = 0. That prefix value was already recorded 1 time, and each occurrence marks a place the subarray can start: A[0..1] = [4, 2]. Everything before those points cancels out, leaving XOR 6. The running count rises to 1.
Prefix through index 2 is 4, so the partner it needs is 4 XOR 6 = 2. No earlier prefix ever equalled 2, so nothing ending at index 2 can carry XOR 6 — the count stays 1. Prefix 4 is filed away anyway, since a later index may need it as its own partner.
Prefix through index 3 is 2, so the partner it needs is 2 XOR 6 = 4. That prefix value was already recorded 2 times, and each occurrence marks a place the subarray can start: A[1..3] = [2, 2, 6] and A[3..3] = [6]. Everything before those points cancels out, leaving XOR 6. The running count rises to 3.
Prefix through index 4 is 6, so the partner it needs is 6 XOR 6 = 0. That prefix value was already recorded 1 time, and each occurrence marks a place the subarray can start: A[0..4] = [4, 2, 2, 6, 4]. Everything before those points cancels out, leaving XOR 6. The running count rises to 4.
Prefix through index 5 is 0, so the partner it needs is 0 XOR 6 = 6. That prefix value was already recorded 2 times, and each occurrence marks a place the subarray can start: A[2..5] = [2, 6, 4, 6] and A[5..5] = [6]. Everything before those points cancels out, leaving XOR 6. The running count rises to 6.
Prefix through index 6 is 2, so the partner it needs is 2 XOR 6 = 4. That prefix value was already recorded 2 times, and each occurrence marks a place the subarray can start: A[1..6] = [2, 2, 6, 4, 6, 2] and A[3..6] = [6, 4, 6, 2]. Everything before those points cancels out, leaving XOR 6. The running count rises to 8.
One pass, every index asked once, and 8 subarrays came out with XOR 6. Checking all 28 subarrays directly would give the same answer in O(n^2); storing prefixes turns each lookup into O(1) and the whole scan into O(n).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Subarrays with given XOR in the editor All Arrays problems Back to roadmap