Practice › Arrays
Count Subarrays with XOR K
Medium · Arrays · Asked at Amazon, Flipkart, Microsoft, Codenation
Print the number of subarrays whose bitwise XOR of all elements equals k.
Input
First line: n k. Second line: n integers.
Output
The number of such subarrays.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i], k ≤ 10^9
Prefix XOR: the subarray (j, i] has XOR k exactly when px[j] = px[i] ^ k. Count earlier prefixes in a hash map.
Example 1
Input
5 6 4 2 2 6 4
Output
4
Example 2
Input
5 5 5 6 7 8 9
Output
2
Hints
- XOR of a[j+1..i] = px[i] ^ px[j], where px is the prefix XOR.
- So for each i you need the number of earlier prefixes equal to px[i] ^ k — keep counts in a hash map (start with px = 0 seen once).
Approach
Same idea as "subarray sum equals K", with XOR instead of sums. Walk the array keeping the running prefix XOR x. Every earlier prefix p with p = x ^ k ends a valid subarray at the current index, so add count[x ^ k], then record x. Initialise count[0] = 1 for subarrays starting at index 0.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long k;
cin >> n >> k;
unordered_map<long long, long long> cnt;
cnt[0] = 1;
long long x = 0, ans = 0, v;
for (int i = 0; i < n; i++) {
cin >> v;
x ^= v;
auto it = cnt.find(x ^ k);
if (it != cnt.end()) ans += it->second;
cnt[x]++;
}
cout << ans << "\n";
return 0;
}Python solution
import sys
from collections import defaultdict
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
cnt = defaultdict(int)
cnt[0] = 1
x = ans = 0
for v in a:
x ^= v
ans += cnt[x ^ k]
cnt[x] += 1
print(ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
HashMap<Long, Long> cnt = new HashMap<>();
cnt.put(0L, 1L);
long x = 0, ans = 0;
for (int i = 0; i < n; i++) {
x ^= sc.nextLong();
ans += cnt.getOrDefault(x ^ k, 0L);
cnt.merge(x, 1L, Long::sum);
}
System.out.println(ans);
}
}Solve Count Subarrays with XOR K online · All practice problems