.png)
Count Subarrays with XOR Equal to K
(Prefix XOR + Hashing)
Problem Statement
You are given an integer array arr and an integer K.
Your task is to count the number of contiguous subarrays whose XOR is exactly equal to K.
Example 1
Input
arr = [4, 2, 2, 6, 4]
K = 6
Output
4
Explanation
Subarrays with XOR = 6:
[4,2]
[2,2,6]
[6]
[4,2,2,6,4]
Example 2
Input
arr = [5, 6, 7, 8, 9]
K = 5
Output
2
Why This Problem Is Important
- Classic Prefix XOR + Hashing problem
- Very frequent in Amazon, Google, Microsoft
- Introduces:
- XOR properties
- Subarray counting logic
- Foundation for:
- Bitwise prefix problems
- Advanced hashing techniques
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix XOR (No Hashing) | O(n²) | O(n) |
| Approach 3 | Prefix XOR + Hash Map (Optimal) | O(n) | O(n) |
Approach 1: Brute Force
Idea
- Try all subarrays
- Compute XOR for each
- Count those equal to K
Time & Space
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {4,2,2,6,4};
int n = 5, K = 6;
int count = 0;
for(int i=0;iC++
#include
using namespace std;
int main() {
vector arr = {4,2,2,6,4};
int K = 6, count = 0;
for(int i=0;iJava
class CountSubarraysXOR {
public static void main(String[] args) {
int[] arr = {4,2,2,6,4};
int K = 6, count = 0;
for(int i=0;iPython
arr = [4,2,2,6,4]
K = 6
count = 0
for i in range(len(arr)):
xr = 0
for j in range(i, len(arr)):
xr ^= arr[j]
if xr == K:
count += 1
print(count)
JavaScript
let arr = [4,2,2,6,4];
let K = 6, count = 0;
for(let i=0;iC#
using System;
class Program {
static void Main() {
int[] arr = {4,2,2,6,4};
int K = 6, count = 0;
for(int i=0;iApproach 2: Prefix XOR (No Hashing)
Idea
- Build prefix XOR array
- XOR of subarray (i, j):
prefix[j] ^ prefix[i-1]
- Check all (i, j)
Time & Space
- Time: O(n²)
- Space: O(n)
Implementations
Python
arr = [4,2,2,6,4]
K = 6
n = len(arr)
prefix = [0]*(n+1)
for i in range(n):
prefix[i+1] = prefix[i] ^ arr[i]
count = 0
for i in range(n):
for j in range(i+1, n+1):
if prefix[j] ^ prefix[i] == K:
count += 1
print(count)
(Logic remains identical for all languages)
Approach 3: Prefix XOR + Hash Map (Optimal)
Idea
Key XOR property:
If prefixXOR ^ K = previousPrefixXOR
Steps:
- Maintain running prefix XOR
- Store frequencies in hash map
- Count matches in O(1)
Time & Space
- Time: O(n)
- Space: O(n)
Implementations (Optimal)
C
#include
int main() {
int arr[] = {4,2,2,6,4};
int n = 5, K = 6;
int freq[1024] = {0}; // assuming XOR range
int xr = 0, count = 0;
freq[0] = 1;
for(int i=0;iC++
#include
using namespace std;
int main() {
vector arr = {4,2,2,6,4};
int K = 6, xr = 0, count = 0;
unordered_map mp;
mp[0] = 1;
for(int x : arr) {
xr ^= x;
count += mp[xr ^ K];
mp[xr]++;
}
cout << count;
}
Java
import java.util.*;
class CountSubarraysXOR {
public static void main(String[] args) {
int[] arr = {4,2,2,6,4};
int K = 6, xr = 0, count = 0;
HashMap map = new HashMap<>();
map.put(0,1);
for(int x : arr) {
xr ^= x;
count += map.getOrDefault(xr ^ K, 0);
map.put(xr, map.getOrDefault(xr, 0) + 1);
}
System.out.println(count);
}
}
Python
arr = [4,2,2,6,4]
K = 6
freq = {0:1}
xr = 0
count = 0
for x in arr:
xr ^= x
count += freq.get(xr ^ K, 0)
freq[xr] = freq.get(xr, 0) + 1
print(count)
JavaScript
let arr = [4,2,2,6,4];
let K = 6;
let xr = 0, count = 0;
let map = new Map();
map.set(0,1);
for(let x of arr){
xr ^= x;
count += map.get(xr ^ K) || 0;
map.set(xr, (map.get(xr) || 0) + 1);
}
console.log(count);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {4,2,2,6,4};
int K = 6, xr = 0, count = 0;
Dictionary map = new Dictionary();
map[0] = 1;
foreach(int x in arr) {
xr ^= x;
if(map.ContainsKey(xr ^ K))
count += map[xr ^ K];
if(map.ContainsKey(xr))
map[xr]++;
else
map[xr] = 1;
}
Console.WriteLine(count);
}
}
Summary
- Brute Force: Concept clarity
- Prefix XOR: Mathematical understanding
- Prefix XOR + Hashing: Interview favorite
- Works with negative numbers
- Core foundation for bitwise subarray problems
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
