Start practising

Subarray with given XOR

Medium Arrays & Hashing Prefix Sum Strategy Original on InterviewBit

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, 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^5
  • 1 <= A[i], B <= 10^9

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 Java code.

ApproachTimeSpace
Brute forceO(n²)O(1)
Optimal (prefix XOR + hash map)O(n)O(n)

1Brute force

TimeO(n²)
SpaceO(1)

Extend every start index with a running XOR and count results equal to B.

  1. For each i, x = 0; for j from i: x ^= A[j]; if x == B, count++.
Java
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;
    }
}

2Optimal (prefix XOR + hash map)

TimeO(n)
SpaceO(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.

  1. freq = {0: 1}.
  2. For each value: px ^= value; count += freq[px ^ B]; freq[px]++.
Java
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;
    }
}

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.

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.