Count Number of Subarrays with Given XOR K

The Count Number of Subarrays with Given XOR K problem requires finding the total count of contiguous subarrays within an integer array whose bitwise XOR sum equals a given target integer $K$. This topic builds upon the prefix sum strategy used in problems like "Subarray Sum Equals K", extending the mathematical properties of XOR arithmetic to achieve an optimal $O(N)$ time complexity using hash maps.

1. Problem Statement & Core Definitions

Given an array of integers arr of size $N$ and an integer $K$, determine the number of contiguous subarrays whose bitwise XOR combination evaluates to $K$.

Key Concept: Contiguous Subarrays

A subarray is defined as a contiguous, unbroken sequence of elements within an array. Non-contiguous selections of elements do not qualify as subarrays.

Array: [4, 2, 2, 6, 4]

Valid Subarrays:
- [4, 2]         (Contiguous elements from index 0 to 1)
- [6]            (Single element at index 3)
- [2, 2, 6]      (Contiguous elements from index 1 to 3)

Invalid Subarrays:
- [4, 6]         (Non-contiguous; skips index 1 and 2)

2. Bitwise XOR Mechanics & Concrete Example

XOR Properties Quick Reference

1. Identity Property: $A \oplus 0 = A$
2. Self-Inverse Property: $A \oplus A = 0$
3. Commutative & Associative: $A \oplus B = B \oplus A$, $(A \oplus B) \oplus C = A \oplus (B \oplus C)$

Example Walkthrough

Consider arr = [4, 2, 2, 6, 4] and K = 6.

We evaluate the XOR sums of various contiguous subarrays:

1. [4, 2] $\rightarrow 4 \oplus 2 = 6$
2. [6] $\rightarrow 6$
3. [2, 2, 6] $\rightarrow 2 \oplus 2 \oplus 6 = (2 \oplus 2) \oplus 6 = 0 \oplus 6 = 6$
4. [4, 2, 2, 6, 4] $\rightarrow 4 \oplus 2 \oplus 2 \oplus 6 \oplus 4 = (4 \oplus 4) \oplus (2 \oplus 2) \oplus 6 = 0 \oplus 0 \oplus 6 = 6$

Total Valid Subarrays = 4.

3. Mathematical Foundation: The Prefix XOR Derivation

To solve this problem efficiently without checking every possible subarray, we utilize prefix XOR properties.

Derivation Steps

1. Let $XR$ be the prefix XOR sum from index 0 up to current index i.
2. Assume there exists a target subarray ending at index i that has a XOR sum equal to $K$.
3. Let $X$ be the prefix XOR sum from index 0 up to the starting boundary of this target subarray.
4. The relationship between these segments can be stated as:

5. To isolate $X$, take the bitwise XOR with $K$ on both sides of the equation:

6. Applying the self-inverse property ($K \oplus K = 0$):

Core Insight: If the current prefix XOR up to index i is $XR$, then any valid target subarray ending at index i with XOR sum $K$ must be preceded by a prefix with XOR sum equal to $X = XR \oplus K$.

4. Naive Generation: Brute Force Approach

The brute-force strategy generates all possible contiguous subarrays using two outer pointers i and j, and uses a third loop k to compute the XOR sum of the subarray between i and j.

Vertical Execution Logic

C++ Implementation (Brute Force)

#include <vector>

int countSubarraysWithXorKBrute(const std::vector<int>& arr, int K) {
    int n = arr.size();
    int count = 0;

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

Complexity Analysis

• Time Complexity: $O(N^3)$ — Three nested loops iterating over the array length $N$.
• Space Complexity: $O(1)$ — Uses only a few primitive variables for tracking iteration and state.

5. Optimizing Subarray Generation: Better Approach

We can reduce one layer of iteration by maintaining a running XOR computation inside the second loop. When expanding the right endpoint j, we incrementally XOR the incoming element arr[j] with the existing XOR sum of arr[i...j-1].

C++ Implementation (Better Approach)

#include <vector>

int countSubarraysWithXorKBetter(const std::vector<int>& arr, int K) {
    int n = arr.size();
    int count = 0;

    for (int i = 0; i < n; i++) {
        int current_xor = 0;
        for (int j = i; j < n; j++) {
            current_xor ^= arr[j];
            if (current_xor == K) {
                count++;
            }
        }
    }
    return count;
}

Complexity Analysis

• Time Complexity: $O(N^2)$ — Two nested loops iterating over the array length $N$.
• Space Complexity: $O(1)$ — Auxiliary space remains constant.

6. Optimal Approach: Prefix XOR with Hash Map

Instead of recomputing or checking subarrays across multiple indices, we can iterate through the array once from left to right while keeping track of:

1. The running cumulative prefix XOR ($XR$).
2. A Hash Map storing the frequency of all prefix XOR values encountered so far.

Algorithm Steps

1. Initialize XR = 0, count = 0.
2. Initialize a hash map m to store {Prefix_XOR: Frequency}.
3. Pre-seed the map with m[0] = 1. This accounts for cases where the prefix XOR $XR$ itself equals $K$ from the start of the array ($XR \oplus K = K \oplus K = 0$).
4. Iterate through each element val in arr:
   • Update running prefix XOR: $XR = XR \oplus val$.
   • Calculate required prefix XOR: $X = XR \oplus K$.
   • Add the frequency of $X$ stored in map m to count (count += m[X]).
   • Increment the frequency of the current prefix XOR $XR$ in map m (m[XR]++).
5. Return total count.

7. Complete Visual Trace Walkthrough

Trace array arr = [4, 2, 2, 6, 4] with target K = 6.

Initial State

• XR = 0, count = 0
• Hash Map: {0: 1}

Final Result: count = 4.

8. Optimal Code Implementations

C++ Source Code

#include <vector>
#include <unordered_map>

int countSubarraysWithXorK(const std::vector<int>& arr, int K) {
    int xr = 0;
    std::unordered_map<int, int> mpp;
    
    // Base condition: XOR sum of 0 has occurred once initially
    mpp[xr] = 1; 
    
    int count = 0;
    
    for (int i = 0; i < arr.size(); i++) {
        // Prefix XOR till current index
        xr = xr ^ arr[i];
        
        // Target value required from the map
        int x = xr ^ K;
        
        // Add frequency of x if it exists in map
        if (mpp.find(x) != mpp.end()) {
            count += mpp[x];
        }
        
        // Store/update current prefix XOR in map
        mpp[xr]++;
    }
    
    return count;
}

Java Source Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static int countSubarraysWithXorK(int[] arr, int K) {
        int xr = 0;
        Map<Integer, Integer> mpp = new HashMap<>();
        
        // Base condition
        mpp.put(xr, 1);
        
        int count = 0;
        
        for (int i = 0; i < arr.length; i++) {
            xr = xr ^ arr[i];
            
            int x = xr ^ K;
            
            if (mpp.containsKey(x)) {
                count += mpp.get(x);
            }
            
            mpp.put(xr, mpp.getOrDefault(xr, 0) + 1);
        }
        
        return count;
    }
}

Python Source Code

def count_subarrays_with_xor_k(arr: list[int], K: int) -> int:
    xr = 0
    mpp = {0: 1}  # Base condition
    count = 0
    
    for num in arr:
        xr ^= num
        x = xr ^ K
        
        if x in mpp:
            count += mpp[x]
            
        mpp[xr] = mpp.get(xr, 0) + 1
        
    return count

9. Complexity Analysis & Map Trade-Offs

Time Complexity

• Using Ordered Map (std::map in C++): $O(N \log N)$
  • Each Insertion and Lookup operation takes $O(\log N)$ time.
• Using Unordered Map (std::unordered_map in C++ / HashMap in Java):
  • Average / Best Case: $O(N)$ — Map operations run in $O(1)$ constant time.
  • Worst Case: $O(N^2)$ — Occurs if heavy hash collisions degrade map lookup to $O(N)$ per element.

Space Complexity

• Auxiliary Space: $O(N)$ worst-case space complexity, as all prefix XOR values stored in the map could be distinct.

10. Comparative Strategy Summary

Summary and Key Takeaways

• Subarray Definition: Subarrays are strictly contiguous elements. Picking non-adjacent elements is invalid.
• Prefix Mathematical Inverse: The relation $X \oplus K = XR$ transforms directly into $X = XR \oplus K$ due to the XOR self-inverse property ($K \oplus K = 0$).
• Single Pass Efficiency: By storing historical prefix XOR frequencies in a hash map, we can check for valid ending subarrays at index i without recalculating previous values.
• Base Case Map Initialization: Pre-populating the map with {0: 1} handles subarrays starting at index 0 whose overall XOR sum $XR$ directly equals $K$.
• Frequency Addition: Always increment count by mpp[X] rather than by 1, because a specific prefix XOR $X$ can occur multiple times earlier in the array.
• Map Selection Trade-offs: Choose between $O(N \log N)$ guaranteed time (std::map) and $O(N)$ average time (unordered_map / HashMap) based on language conventions and collision considerations.