Count Subarrays with XOR K
Count Subarrays with XOR K is a GFG problem (Medium), listed there as Count Subarrays with given XOR; it has no LeetCode number of its own. You are given an array arr of non-negative integers and an integer k. Return how many subarrays have a bitwise XOR equal to k.
- A subarray is a contiguous, non-empty run of elements. Two subarrays with the same values at different positions count separately.
- The XOR of a subarray is all of its elements combined with
^. - The array can hold up to 10⁵ elements. There are about n²/2 subarrays, so listing them is too slow, and the answer itself can exceed the range of a 32-bit int.
- 1 <= arr.length <= 10⁵
- 0 <= arr[i] <= 10⁵
- 0 <= k <= 10⁵
Intuition
Describe a subarray by two prefixes instead of by its two ends. Let P[j] be the XOR of arr[0..j], with P[-1] = 0 for the empty prefix. Because x ^ x = 0, the elements two prefixes share cancel out:
XOR(arr[i+1..j]) = P[j] ^ P[i]
Setting that equal to k and XOR-ing both sides with P[j] turns it around: P[i] = P[j] ^ k. So the number of good subarrays ending at j is simply how many earlier prefixes equal P[j] ^ k. A hash map from prefix value to how often it has appeared answers that in one lookup, which turns O(n²) pairs into one pass.
"Count subarrays whose combined value equals k" where the combining operation can be undone (+ undone by -, ^ undone by ^) is the prefix + frequency map pattern. To count subarrays with given XOR k, swap - for ^ in the subarray-sum-equals-k solution. The pattern does not apply to AND or OR, because those cannot be undone.
Approach
Before reading on: write the XOR of arr[i+1..j] using two prefix XORs, solve it for the earlier prefix, and decide what the map must hold before the first element is read. Aim for O(n) time.
Two ways to solve it
Keep a running prefix XOR and a map of how often each prefix has appeared; add the count of prefix ^ k at every index.
- Passes: one.
- Memory: up to n + 1 map entries.
- Scale: 10⁵ elements in a blink.
The answer expected in an interview.
Fix each start i, extend the end j with a running XOR, and count every time it equals k.
- Passes: one per start index.
- Memory: two counters.
- Scale: about 5 × 10⁹ steps at n = 10⁵.
A good first answer to state, then improve.
The map trades O(n) memory for dropping a whole loop, which is what makes 10⁵ elements feasible. The steps, code and live demo below follow the prefix XOR version; the brute-force code comes after the demo.
Seed the map with the empty prefix
seen = {0: 1}, prefix = 0, count = 0. The entry 0: 1 is the empty prefix before index 0. Without it, a subarray that starts at index 0 has no earlier prefix to pair with and is never counted.
Extend the prefix XOR
For each x, do prefix ^= x. Now prefix is the XOR of everything from index 0 to here: the P[j] that the lookup pairs with an earlier prefix.
Count the subarrays ending here
count += seen.get(prefix ^ k, 0). Every earlier prefix equal to prefix ^ k marks a different start, so add the whole count, not 1.
Record this prefix, after the lookup
seen[prefix] += 1. Recording only after the lookup means the current prefix is never paired with itself, which would count an empty subarray when k = 0.
Count Subarrays with XOR K solution in Python | C++ | Java
seen = {0: 1}. The XOR of nothing is 0, and that empty prefix sits before index 0. A subarray starting at index 0 pairs with it; without this entry such subarrays would never be counted.seen = {0: 1}. The XOR of nothing is 0, and that empty prefix sits before index 0. A subarray starting at index 0 pairs with it; without this entry such subarrays would never be counted.seen = {0: 1}. The XOR of nothing is 0, and that empty prefix sits before index 0. A subarray starting at index 0 pairs with it; without this entry such subarrays would never be counted.Brute force with a running XOR
For every start index, the inner loop extends the subarray one element at a time and keeps its XOR up to date, so each subarray is checked in O(1).
Common pitfalls
Starting with an empty map
seen = {}seen = {0: 1}A subarray starting at index 0 has XOR equal to the prefix itself, so it needs P[-1] = 0 as its partner. Without the seed, [6] with k = 6 returns 0 instead of 1.
Using a set instead of a counter
if prefix ^ k in seen_set:
count += 1count += seen.get(prefix ^ k, 0)
If the needed prefix appeared at three earlier positions, three different subarrays end here. A set can only say yes or no, so it undercounts whenever a prefix value repeats, which is common with small values.
Updating the map before the lookup
prefix ^= x seen[prefix] = seen.get(prefix, 0) + 1 count += seen.get(prefix ^ k, 0)
prefix ^= x count += seen.get(prefix ^ k, 0) seen[prefix] = seen.get(prefix, 0) + 1
When k = 0, prefix ^ k is prefix, so the prefix just added matches itself and every position counts one extra empty subarray. For other k the order happens not to matter, which hides the bug.
Keeping the answer in a 32-bit int
int count = 0;
long count = 0;
With n = 10⁵ and every element 0, k = 0, every one of the n(n + 1)/2 ≈ 5 × 10⁹ subarrays counts. That overflows int in C++ and Java; the map's counts can stay int, the running total cannot.
Complexity
Count subarrays with XOR k vs. its look-alikes
These share the prefix + hash map idea but differ in the operator, what the map stores, and the seed.
| Problem | Partner prefix | Map stores | Seed |
|---|---|---|---|
| Count subarrays with XOR k | prefix ^ k | how many times seen | {0: 1} |
| Subarray Sum Equals K (LeetCode 560) | prefix − k | how many times seen | {0: 1} |
| Longest subarray with sum k | prefix − k | first index seen | {0: −1} |
Count Subarrays with XOR K FAQ
Is there a count subarrays with xor k LeetCode problem?
Not under that name; it comes from GFG and Striver's A2Z sheet. The closest LeetCode problems are 560 Subarray Sum Equals K (same pattern with -) and 1442 Count Triplets That Can Form Two Arrays of Equal XOR, which counts pairs of equal prefix XORs, the k = 0 case.
What does the count subarrays with xor k Python code look like with a Counter?
Use collections.Counter: seen = Counter({0: 1}), then in the loop prefix ^= x, count += seen[prefix ^ k], seen[prefix] += 1. A Counter returns 0 for missing keys, so the .get(..., 0) calls disappear.