Problem link - https://www.geeksforgeeks.org/problems/count-subarray-with-given-xor/1
One of the most frequently asked hashing problems in interviews is counting the number of subarrays having a given XOR value K.
The brute force solution is straightforward, but the optimal approach uses a beautiful combination of Prefix XOR and HashMap to achieve linear time complexity.
Problem Statement
Given an array arr[] and an integer k, count the number of subarrays whose XOR is equal to k.
Example
Input:
arr = [4, 2, 2, 6, 4]
k = 6
Output:
4
Subarrays having XOR = 6:
[4, 2]
[2, 2, 6]
[6]
[4, 2, 2, 6, 4]
Total count = 4
Brute Force Approach
Generate every possible subarray and calculate its XOR.
Interview Explanation
For every starting index, keep extending the subarray towards the right while maintaining the current XOR. Whenever the XOR becomes k, increment the count.
Complexity
- Time Complexity: O(N²)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public long subarrayXor(int[] arr, int k) {
long count = 0;
for (int i = 0; i < arr.length; i++) {
int xor = 0;
for (int j = i; j < arr.length; j++) {
xor ^= arr[j];
if (xor == k) {
count++;
}
}
}
return count;
}
}
Optimal Approach: Prefix XOR + HashMap
Key Observation
For Sum problems, we use:
prefixSum - k
For XOR problems, we use:
prefixXor ^ k
Suppose:
prefixXor = XOR from index 0 to i
and some previous prefix XOR is:
oldPrefixXor
Then:
oldPrefixXor ^ prefixXor = k
Using XOR properties:
oldPrefixXor = prefixXor ^ k
Therefore, for every index, we simply need to know how many times (prefixXor ^ k) has appeared before.
A HashMap helps us find this frequency in O(1).
Why Store Frequency Instead of Index?
The question asks us to:
Count subarrays
not
Find longest subarray
Therefore we store:
prefixXor -> frequency
Every previous occurrence contributes one valid subarray ending at the current index.
Dry Run
arr = [4, 2, 2, 6, 4]
k = 6
Initialize:
map = {0 : 1}
xor = 0
count = 0
Index 0
xor = 4
need = 4 ^ 6 = 2
Not found.
Store:
map = {0:1, 4:1}
Index 1
xor = 6
need = 6 ^ 6 = 0
Found once.
count = 1
Subarray:
[4, 2]
Index 2
xor = 4
need = 4 ^ 6 = 2
Not found.
Store frequency of 4.
Index 3
xor = 2
need = 2 ^ 6 = 4
4 exists twice.
count += 2
Subarrays:
[2, 2, 6]
[6]
Index 4
xor = 6
need = 6 ^ 6 = 0
0 exists once.
count += 1
Subarray:
[4, 2, 2, 6, 4]
Final answer:
count = 4
Optimal Java Solution
class Solution {
public long subarrayXor(int[] arr, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int xor = 0;
long count = 0;
map.put(0, 1);
for (int num : arr) {
xor ^= num;
int need = xor ^ k;
count += map.getOrDefault(need, 0);
map.put(xor, map.getOrDefault(xor, 0) + 1);
}
return count;
}
}
Complexity Analysis
- Time Complexity: O(N)
- Space Complexity: O(N)
Key Takeaway
Whenever you see:
Count subarrays with XOR = K
Think:
oldPrefixXor = currentPrefixXor ^ k
Store prefix XOR frequencies in a HashMap and count matching occurrences in O(N) time.
