Prefix XOR — Subarrays with XOR = K

What does it solve?

Count contiguous subarrays whose XOR equals K. Define prefix XOR X[i] = a[0] ⊕ … ⊕ a[i]. Because XOR is its own inverse, the XOR of a range (j, i] is X[i] ⊕ X[j].

Key insight: a subarray ending at i has XOR K exactly when an earlier prefix equals X[i] ⊕ K (rearranged from X[j] = X[i] ⊕ K). Count prefixes in a hash map, look up in O(1). Identical shape to prefix sum, swap + for ⊕ and − for ⊕.

The core idea

// XOR is its own inverse
count = {0: 1}
px = 0, ans = 0
for x in nums:
  px ^= x
  ans += count[px ^ k] // need
  count[px] += 1

Complexity

Time complexity

O(N)

One sweep. Each XOR, lookup, and insert is O(1) on average.

Space complexity

O(N)

Hash map of distinct prefix-XOR values, up to N in the worst case.

Examples & edge cases

Live animation — running prefix XOR + count map

current element matched subarray map hit → count +=

Array — prefix XOR under each cell

count map — prefixXOR → times seen

i = — px = — need = — count = —

Step — of —

index i

—

current element

prefix XOR

—

running ⊕

need (px ⊕ k)

—

look up in map

Subarrays found

—

running total

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	i	num	px	need	hits	Action	count

C++ implementation

subarray_xor_k.cpp

#include <bits/stdc++.h>
using namespace std;

// Count subarrays with XOR equal to k
long long subarrayXor(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;              // empty prefix XOR = 0
    int px = 0;
    long long ans = 0;

    for (int x : nums) {
        px ^= x;                    // extend prefix XOR
        int need = px ^ k;           // prefix we'd need earlier
        if (count.count(need)) ans += count[need];
        count[px]++;
    }
    return ans;
}

int main() {
    vector<int> nums = {4, 2, 2, 6, 4};
    cout << subarrayXor(nums, 6) << "\n"; // 4
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save... 0 chars