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, 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^5
  • 1 <= 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.

00:00
Testcase

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.

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++.
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]++.
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, 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.