Count Subarrays with given XOR

You're given an array of integers arr and an integer k. Count the number of subarrays whose elements XOR together to exactly k.

A subarray is a contiguous slice of the array — [2, 2, 6] counts, but you can't skip elements.

It is guaranteed that the total count fits within a 32-bit integer.

Hints

· Stuck? Reveal one nudge at a time.

Checking every subarray works but is O(n^2). What running quantity could let you describe any subarray using just two values?

XOR cancels itself: a ^ a = 0. So the XOR of arr[i..j] equals prefixXor[j] ^ prefixXor[i-1] — the shared prefix vanishes.

You need prefixXor[i-1] = prefixXor[j] ^ k. Keep a hash map from each prefix XOR value to how many times it has appeared, seeded with {0: 1}, and add freq[prefix ^ k] at every step.

Common doubts

The empty prefix (before any element) has XOR 0. Seeding freq[0] = 1 lets subarrays that start at index 0 find their partner — without it, a whole-array match would be missed.

Several earlier positions can share the same prefix XOR, and each one is the start of a different valid subarray ending here. Adding freq[prefix ^ k] counts all of them at once.

Nothing in the code — but conceptually you are counting pairs of equal prefix snapshots, since prefix ^ 0 = prefix. That is why the update order matters: look up before inserting the current prefix, or it would match itself.

Yes — replace prefix ^= num with prefix += num and look up prefix - k, and you have solved Subarray Sum Equals K. The prefix-plus-hash-map skeleton is identical.

Interview follow-ups

· What an interviewer asks next.

A hash map can only answer equality lookups. For range queries over XOR you switch the data structure to a binary trie of prefix XORs, walking bit by bit and counting whole subtrees that are guaranteed below k.

Store the earliest index of each prefix XOR instead of a frequency. At each position, if prefix ^ k was seen before, the candidate length is the gap to its first occurrence — keep the maximum.

Map each prefix XOR to the list of indices where it occurred. Each stored index i with value prefix ^ k yields the subarray from i + 1 to the current position — but note the output itself can be O(n^2) in size.

Fun facts

XOR is the only operator here that is its own inverse — that self-cancellation (a ^ a = 0) is the entire reason prefixes subtract cleanly without any actual subtraction.
The prefix-plus-hash-map skeleton is one of the highest-leverage patterns in interviews: it solves Subarray Sum Equals K, Longest Sub-Array with Sum K, and this problem with only the operator swapped.
The follow-up world of this trick — XOR range queries — is dominated by binary tries, the same structure behind Maximum XOR of Two Numbers in an Array.

Asked at

AmazonGoogleMicrosoftFlipkartAdobe

Frequently Sometimes Occasionally

Example 1

Input: arr = [4, 2, 2, 6, 4], k = 6
Output: 4
Four subarrays XOR to 6: [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], and [6].

Example 2

Input: arr = [5, 6, 7, 8, 9], k = 5
Output: 2
Only [5] and the full array [5, 6, 7, 8, 9] XOR to 5.

Example 3

Input: arr = [1, 1, 1, 1], k = 0
Output: 4
The three [1, 1] pairs and the whole array [1, 1, 1, 1] each XOR to 0.

Constraints

- 1 <= arr.size <= 10^5 - 0 <= arr[i] <= 10^5 - 0 <= k <= 10^5

This problem is the XOR twin of Subarray Sum Equals K — and mastering it teaches you the single most reusable trick in subarray counting: turn a range question into a two-point question with prefixes, then count matches with a hash map.

Prerequisites

Before you start

· Concepts used directly in the solution.

XOR basics. XOR is its own inverse — a ^ a = 0 and a ^ 0 = a — which is exactly what lets prefixes cancel.

Prefix accumulation. A running value over arr[0..i] lets you express any subarray in terms of two prefix values.

Hash map counting. Storing how many times each prefix value has appeared turns a lookback scan into an O(1) lookup.

Understand the problem

In plain English: count the contiguous slices of arr whose elements XOR to k.

Formally: count the pairs (i, j) with 0 <= i <= j < n such that arr[i] ^ arr[i+1] ^ ... ^ arr[j] == k.

Worked example — arr = [4, 2, 2, 6, 4], k = 6

index:    0   1   2   3   4
arr:      4   2   2   6   4
prefix:   4   6   4   2   6     (running XOR)

[4,2]        = 4^2         = 6  ✓
[2,2,6]      = 2^2^6       = 6  ✓
[6]          = 6            = 6  ✓
[4,2,2,6,4]  = 4^2^2^6^4   = 6  ✓
answer: 4

Clarifying questions

A senior engineer confirms the contract before writing a line of code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can k be 0?”

Yes — and it matters. A subarray XORs to 0 exactly when two prefix snapshots are equal, so your method must handle repeated prefix values, not just distinct ones.

“Can elements repeat?”

Yes. Duplicates are common and they are what produces multiple subarrays with the same XOR.

Edge cases

“Does a single element count as a subarray?”

Yes — [6] alone is a valid answer when arr[i] == k.

“What if no subarray XORs to k?”

Return 0 — the count can legitimately be zero.

Constraints & scale

“How large can the array get?”

Up to 10^5 elements. That rules out checking all O(n^2) subarrays (~5 billion XOR operations in the worst case) and demands a linear or near-linear approach.

“Can the count overflow?”

The statement guarantees the total fits in a 32-bit integer, so a plain int is safe.

The ideal opening — say it like this

Before I start, I have a few clarifying questions.

Can k be zero, and can elements repeat? I ask because both affect how I count matching prefixes.

And with n up to ten to the fifth, I should aim for a linear-time solution rather than checking every subarray.

Key observations

1Aha

Every subarray XOR is a difference of two prefix XORs

Let P[j] be the XOR of arr[0..j] (and P[-1] = 0). Because XOR cancels itself, the shared prefix arr[0..i-1] vanishes:

XOR(arr[i..j]) = P[j] ^ P[i-1]

P[j]   = (arr[0]..arr[i-1]) ^ (arr[i]..arr[j])
P[i-1] = (arr[0]..arr[i-1])
XOR them → the common part cancels, the subarray remains

A question about O(n^2) subarrays just became a question about pairs of prefix values.

2Aha

Solve for the partner you need

You want P[j] ^ P[i-1] = k. XOR both sides by P[j]: you need P[i-1] = P[j] ^ k. So standing at index j, the earlier prefixes that complete a valid subarray are exactly those equal to P[j] ^ k — a single value you can look up.

3Aha

A frequency map counts all partners at once

Store how many times each prefix value has occurred in a hash map (seeding {0: 1} for the empty prefix, so subarrays starting at index 0 are counted). At each step, freq[prefix ^ k] tells you — in O(1) — how many valid subarrays end right here. One pass, done.

Brute force vs optimal

	Brute force	Optimal
Idea	Running XOR from every start index	Prefix XOR + frequency map
Time	O(n^2)	O(n)
Space	O(1)	O(n)

Full, commented code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

To count subarrays with a target aggregate, convert each subarray into a pair of prefixes, solve for the partner prefix you need, and count partners with a hash map as you sweep. The same skeleton solves Subarray Sum Equals K — only the operator changes from +/- to ^.

freq = {0: 1}          # empty prefix seen once
prefix = 0, count = 0
for num in arr:
    prefix ^= num
    count += freq[prefix ^ k]   # partners that complete a k-subarray
    freq[prefix] += 1
return count