Subarray with given XOR
Subarray with given XOR is a medium arrays & hashing problem solved with the prefix sum strategy pattern.
The best approach, optimal (prefix xor + hash map), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
Given an integer array A and an integer B, count the subarrays whose bitwise XOR equals B.
Examples
Example 1
- Input
A = [4, 2, 2, 6, 4], B = 6- Output
4- Why
- [4,2], [4,2,2,6,4], [2,2,6] and [6].
Example 2
- Input
A = [5, 6, 7, 8, 9], B = 5- Output
2- Why
- [5] and [5,6,7,8,9].
Constraints
1 <= A.length <= 10^51 <= A[i], B <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Optimal (prefix XOR + hash map) | O(n) | O(n) |
1Brute force
O(n²)O(1)Extend every start index with a running XOR and count results equal to B.
- For each i, x = 0; for j from i: x ^= A[j]; if x == B, count++.
class Solution {
public int solve(int[] A, int B) {
int count = 0;
for (int i = 0; i < A.length; i++) {
int x = 0;
for (int j = i; j < A.length; j++) {
x ^= A[j];
if (x == B) count++;
}
}
return count;
}
}class Solution:
def solve(self, A: List[int], B: int) -> int:
count = 0
for i in range(len(A)):
x = 0
for j in range(i, len(A)):
x ^= A[j]
if x == B:
count += 1
return countclass Solution {
public:
int solve(vector<int>& A, int B) {
int count = 0;
for (int i = 0; i < (int) A.size(); i++) {
int x = 0;
for (int j = i; j < (int) A.size(); j++) {
x ^= A[j];
if (x == B) count++;
}
}
return count;
}
};function solve(A, B) {
let count = 0;
for (let i = 0; i < A.length; i++) {
let x = 0;
for (let j = i; j < A.length; j++) {
x ^= A[j];
if (x === B) count++;
}
}
return count;
}2Optimal (prefix XOR + hash map)
O(n)O(n)Same shape as Subarray Sum Equals K, with XOR in place of subtraction. If the prefix XOR so far is px, an earlier prefix equal to px ^ B marks the start of a subarray whose XOR is B.
- freq = {0: 1}.
- For each value: px ^= value; count += freq[px ^ B]; freq[px]++.
class Solution {
public int solve(int[] A, int B) {
Map<Integer, Integer> freq = new HashMap<>();
freq.put(0, 1);
int px = 0, count = 0;
for (int a : A) {
px ^= a;
count += freq.getOrDefault(px ^ B, 0);
freq.merge(px, 1, Integer::sum);
}
return count;
}
}class Solution:
def solve(self, A: List[int], B: int) -> int:
freq = {0: 1}
px, count = 0, 0
for a in A:
px ^= a
count += freq.get(px ^ B, 0)
freq[px] = freq.get(px, 0) + 1
return countclass Solution {
public:
int solve(vector<int>& A, int B) {
unordered_map<int, int> freq;
freq[0] = 1;
int px = 0, count = 0;
for (int a : A) {
px ^= a;
auto it = freq.find(px ^ B);
if (it != freq.end()) count += it->second;
freq[px]++;
}
return count;
}
};function solve(A, B) {
const freq = new Map();
freq.set(0, 1);
let px = 0, count = 0;
for (const a of A) {
px ^= a;
count += freq.get(px ^ B) || 0;
freq.set(px, (freq.get(px) || 0) + 1);
}
return count;
}Edge cases to test
- The subarray starts at index 0 (seed prefix XOR 0 with count 1)
- B equals a single element
Hints
Hint 1
XOR undoes itself: xor(i..j) = px[j] ^ px[i - 1]. For each j, which earlier prefix do you need?
FAQ
What is the best time complexity for Subarray with given XOR?
Optimal (prefix XOR + hash map) runs in O(n) time and O(n) extra space.
Which pattern does Subarray with given XOR use?
It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Range Sum Query - Immutable, Continuous Subarray Sum.
Is there a brute force solution for Subarray with given XOR?
Yes. Brute force takes O(n²) time and O(1) space. Extend every start index with a running XOR and count results equal to B.
Which edge cases should I test for Subarray with given XOR?
The subarray starts at index 0 (seed prefix XOR 0 with count 1); B equals a single element.