Subarray with Given XOR — Find the Range

What does it solve?

Count every contiguous subarray whose elements XOR to a target K. Brute force checks all O(N²) ranges. The trick: a running prefix XOR and the identity that a range (j, i] XORs to px[i] ⊕ px[j].

Key insight: we want that range XOR to equal K, so we need an earlier prefix px ⊕ K. Count how many times each prefix appeared in a hash map and add on the fly. One pass, O(N).

The core idea

// prefix XOR + count map
freq = {0: 1}
px = 0, ans = 0
for x in nums:
  px ^= x
  ans += freq[px ^ k] // need
  freq[px] += 1

Complexity

Time complexity

O(N)

Single sweep with O(1) hash-map lookups and inserts per element.

Space complexity

O(N)

The frequency map stores up to N distinct prefix-XOR values.

Examples & edge cases

Live animation — prefix XOR + count map

current element matched subarray map hit → count +=

Array — prefix XOR under each cell

freq 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_given_xor.cpp

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

// Count subarrays whose XOR equals k
long long countSubarraysXor(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    freq[0] = 1;              // empty prefix
    int px = 0;
    long long ans = 0;

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

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

My Notes

📝Notes✅

▼

●Start typing to save... 0 chars