Count subarrays with given xor K

Given an array of integers nums and an integer k, return the total number of subarrays whose XOR equals to k.

Brute Force#

Fix a start index i and accumulate the XOR of elements from i to j. The trick is to initialize x = k and XOR in each nums[j]; when x == 0, the XOR of the window nums[i..j] equals k. This checks all O(n²) subarrays in O(1) space but is too slow for large inputs, motivating the prefix-XOR hash-map approach below.

class Solution{
public:
    int subarraysWithXorK(vector<int> &nums, int k) {
        int n = nums.size();
        int count = 0;

        for(int i = 0; i < n; i++){
            int x = k;
            for(int j = i; j < n; j++){
                x ^= nums[j];
                if(x==0)
                    count++;
            }
        }
        return count;
    }
};

Time Complexity: O(n^2)

Space Complexity - O(1)

Better Approach#

Use a prefix-XOR hash map, mirroring the prefix-sum approach for count-subarrays-with-given-sum. Define prefixXor as the cumulative XOR up to index i. The XOR of subarray nums[l..r] equals prefixXor[r] ^ prefixXor[l-1]. We want this to equal k, which rearranges to prefixXor[l-1] = prefixXor[r] ^ k. For each index, look up prefixXor ^ k in a map of previously seen prefix XORs and add the count. A single pass with O(1) map operations reduces time to O(n) at the cost of O(n) extra space for the map.