Count Subarrays with XOR K Using Hash Map | Optimal O(N) Solution

Problem Statement: Subarrays with XOR K

Given an array of integers nums and an integer k, your task is to find the total number of continuous subarrays whose bitwise XOR of all elements is equal to k.

Example 1

• Input: nums = [4, 2, 2, 6, 4], k = 6
• Output: 4
• Explanation: The subarrays that satisfy the condition are:
  1. [4, 2] (4 ^ 2 = 6)
  2. [6]
  3. [4, 2, 2, 6, 4] (4 ^ 2 ^ 2 ^ 6 ^ 4 = 6)
  4. [2, 2, 6] (2 ^ 2 ^ 6 = 6)

Example 2

• Input: nums = [5, 6, 7, 8, 9], k = 5
• Output: 2
• Explanation: The subarrays are [5] and [5, 6, 7, 8, 9] (5 ^ 6 ^ 7 ^ 8 ^ 9 = 5).

Constraints

• $1 \le \text{nums.length} \le 10^5$
• $0 \le \text{nums}[i] \le 10^6$
• $0 \le k \le 10^6$

Intuition

A subarray is defined by its start index $i$ and end index $j$. To find all subarrays with a specific XOR value $k$:

1. We iterate through every possible starting point $i$ from $0$ to $n-1$.
2. We then iterate through every possible endpoint $j$ from $i$ to $n-1$.
3. As we expand the window from $i$ to $j$, we maintain a cumulative XOR value.
4. If the cumulative XOR equals $k$, we increment our counter.

Since we are manually checking every single possible range $[i, j]$, we cover all combinations.

Algorithm

1. Initialize count = 0.
2. Use an outer loop ($i$) from $0$ to $n-1$ to fix the starting point of the subarray.
3. Inside, initialize current_xor = 0.
4. Use an inner loop ($j$) from $i$ to $n-1$ to expand the subarray.
5. In each step of the inner loop, update current_xor using the XOR operator: current_xor ^= nums[j].
6. Compare current_xor with k. If they are equal, increment count.
7. Return count after both loops complete.

c++ code

class Solution {
public:
    int solve(vector<int>& nums, int k) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            int current_xor = 0;
            for (int j = i; j < n; j++) {
                current_xor ^= nums[j];
                
                if (current_xor == k) {
                    count++;
                }
            }
        }
        return count;
    }
};

Dry Run:

Array: [4, 2, 2, 6, 4]
Target XOR (k): 6

🔄 Start i = 0

├─ [4]
│  XOR = 4
│  ❌ Not Equal to 6
│
├─ [4, 2]
│  XOR = 4 ^ 2 = 6
│  ✅ Found Subarray
│  Count = 1
│
├─ [4, 2, 2]
│  XOR = 6 ^ 2 = 4
│  ❌ Not Equal to 6
│
├─ [4, 2, 2, 6]
│  XOR = 4 ^ 6 = 2
│  ❌ Not Equal to 6
│
└─ [4, 2, 2, 6, 4]
   XOR = 2 ^ 4 = 6
   ✅ Found Subarray
   Count = 2

──────────────────────────────

🔄 Start i = 1

├─ [2]
│  XOR = 2
│  ❌
│
├─ [2, 2]
│  XOR = 2 ^ 2 = 0
│  ❌
│
├─ [2, 2, 6]
│  XOR = 0 ^ 6 = 6
│  ✅ Found Subarray
│  Count = 3
│
└─ [2, 2, 6, 4]
   XOR = 6 ^ 4 = 2
   ❌

──────────────────────────────

🔄 Start i = 2

├─ [2]
│  XOR = 2
│  ❌
│
├─ [2, 6]
│  XOR = 2 ^ 6 = 4
│  ❌
│
└─ [2, 6, 4]
   XOR = 4 ^ 4 = 0
   ❌

──────────────────────────────

🔄 Start i = 3

├─ [6]
│  XOR = 6
│  ✅ Found Subarray
│  Count = 4
│
└─ [6, 4]
   XOR = 6 ^ 4 = 2
   ❌

──────────────────────────────

🔄 Start i = 4

└─ [4]
   XOR = 4
   ❌

──────────────────────────────

🎯 Matching Subarrays

✅ [4, 2]
✅ [4, 2, 2, 6, 4]
✅ [2, 2, 6]
✅ [6]

🏁 FINAL ANSWER = 4

Complexity Analysis

• Time Complexity: $O(n^2)$ because the nested loops explore all possible pairs of indices.
• Space Complexity: $O(1)$ as we only store the count and the running XOR variable.

Optimal solution

The Intuition

To understand this, you need to know one key property of XOR: If a ^ b = c, then a ^ c = b.

1. We maintain a running XOR total (current_xor) as we traverse the array.
2. We want to find a subarray $[i, j]$ such that:$$\text{PrefixXOR}_j \oplus \text{PrefixXOR}_{i-1} = k$$
3. By rearranging the XOR properties, we look for:$$\text{PrefixXOR}_j \oplus k = \text{PrefixXOR}_{i-1}$$

This means as we move through the array, at each step j, we simply check our Hash Map: "Have I seen a previous prefix XOR value equal to current_xor ^ k?" If yes, those occurrences represent valid subarrays ending at j.

The Algorithm

• Initialize: * count = 0
  • current_xor = 0
  • freq = {0: 1} (This handles the case where the subarray starts from index 0).
• Iterate: For each num in nums:
  • current_xor ^= num
  • target = current_xor ^ k
  • If target is in freq, count += freq[target]
  • freq[current_xor]++ (Store/update the current XOR frequency in the map).
• Return: count.

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraysWithXorK(vector<int>& nums, int k) {
        int count = 0;
        int current_xor = 0;
        // Map to store frequency of prefix XORs
        unordered_map<int, int> freq;
        
        // Base case: prefix XOR of 0 has appeared once
        freq[0] = 1;
        
        for (int num : nums) {
            current_xor ^= num;
            
            // If (current_xor ^ k) exists in the map, add its frequency
            if (freq.count(current_xor ^ k)) {
                count += freq[current_xor ^ k];
            }
            
            // Store the current prefix XOR in the map
            freq[current_xor]++;
        }
        
        return count;
    }
};

Dry run

Complexity Analysis: Optimal XOR Approach

1. Time Complexity: $O(n)$

• Single Pass: We iterate through the array nums exactly once. If the array has $n$ elements, the loop runs $n$ times.
• Hash Map Operations: Inside the loop, we perform two main operations:
  • freq.count(target): Checks if the complement exists in the map.
  • freq[current_xor]++: Updates the map with the new prefix XOR.
• Efficiency: Because we use an unordered_map (implemented as a Hash Table), both search and insertion operations take $O(1)$ time on average.
• Calculation: $n \text{ (iterations)} \times O(1) \text{ (map operations)} = O(n)$.

2. Space Complexity: $O(n)$

• Hash Map Storage: We store the frequencies of prefix XOR values in the map.
• Worst Case: In the worst-case scenario (e.g., an array where every prefix XOR value is distinct), the map will contain $n+1$ entries.
• Calculation: Since the space used by the map grows linearly with the input size $n$, the space complexity is $O(n)$.

Problem link:

Subarrays with XOR ‘K’ - Naukri Code 360

video reference:

https://youtu.be/eZr-6p0B7ME?si=6KH2BsKcob3uZkoQ