Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count subarrays with given XOR

HARDProblemSolveExternal Links

Description

Given an array of integers arr[] and an integer k, count the number of subarrays whose bitwise XOR of all elements equals k.

A subarray is a contiguous part of the array, formed by selecting one or more consecutive elements while maintaining their original order. The XOR of a subarray is computed by applying the bitwise XOR operator (⊕) to every element in that subarray.

Return the total count of such subarrays.

Examples

Example 1

Input: arr = [4, 2, 2, 6, 4], k = 6

Output: 4

Explanation: The subarrays whose XOR equals 6 are:

  • [4, 2] → 4 ⊕ 2 = 6
  • [4, 2, 2, 6, 4] → 4 ⊕ 2 ⊕ 2 ⊕ 6 ⊕ 4 = 6
  • [2, 2, 6] → 2 ⊕ 2 ⊕ 6 = 6
  • [6] → 6

Total count = 4.

Example 2

Input: arr = [5, 6, 7, 8, 9], k = 5

Output: 2

Explanation: The subarrays whose XOR equals 5 are:

  • [5] → 5
  • [5, 6, 7, 8, 9] → 5 ⊕ 6 ⊕ 7 ⊕ 8 ⊕ 9 = 5

Total count = 2.

Example 3

Input: arr = [1, 1, 1, 1], k = 0

Output: 4

Explanation: XOR of two identical numbers is 0. The subarrays with XOR 0 are:

  • [1, 1] (indices 0-1) → 1 ⊕ 1 = 0
  • [1, 1] (indices 1-2) → 1 ⊕ 1 = 0
  • [1, 1] (indices 2-3) → 1 ⊕ 1 = 0
  • [1, 1, 1, 1] (indices 0-3) → 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0

Total count = 4.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • 0 ≤ arr[i] ≤ 10^5
  • 0 ≤ k ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward approach is to examine every possible subarray, compute the XOR of its elements, and check whether the result equals k.

Think of it like testing every possible stretch of a number line. You pick a starting point, then extend rightward one element at a time. As you add each new element, you XOR it into a running value. Whenever that running XOR equals k, you have found a qualifying subarray.

Because XOR is cumulative — you can maintain a running XOR as you extend the subarray (just like a running sum) — you do not need to recompute from scratch each time. This makes the brute force O(n²) rather than O(n³).

Step-by-Step Explanation

Let's trace through arr = [4, 2, 2, 6, 4], k = 6:

Step 1: Initialize count = 0.

Step 2: Start with i = 0, xorVal = 0.

  • j = 0: xorVal = 0 ⊕ 4 = 4. Is 4 == 6? No.
  • j = 1: xorVal = 4 ⊕ 2 = 6. Is 6 == 6? YES! count = 1.
  • j = 2: xorVal = 6 ⊕ 2 = 4. Not 6.
  • j = 3: xorVal = 4 ⊕ 6 = 2. Not 6.
  • j = 4: xorVal = 2 ⊕ 4 = 6. Is 6 == 6? YES! count = 2.

Step 3: Move to i = 1, xorVal = 0.

  • j = 1: xorVal = 0 ⊕ 2 = 2. Not 6.
  • j = 2: xorVal = 2 ⊕ 2 = 0. Not 6.
  • j = 3: xorVal = 0 ⊕ 6 = 6. Is 6 == 6? YES! count = 3.
  • j = 4: xorVal = 6 ⊕ 4 = 2. Not 6.

Step 4: Move to i = 2, xorVal = 0.

  • j = 2: xorVal = 0 ⊕ 2 = 2. Not 6.
  • j = 3: xorVal = 2 ⊕ 6 = 4. Not 6.
  • j = 4: xorVal = 4 ⊕ 4 = 0. Not 6.

Step 5: Move to i = 3, xorVal = 0.

  • j = 3: xorVal = 0 ⊕ 6 = 6. Is 6 == 6? YES! count = 4.
  • j = 4: xorVal = 6 ⊕ 4 = 2. Not 6.

Step 6: Move to i = 4, xorVal = 0.

  • j = 4: xorVal = 0 ⊕ 4 = 4. Not 6.

Result: count = 4.

Brute Force — Checking XOR of All Subarrays — Watch how we fix each starting index i, then extend j rightward, maintaining a running XOR. Each time the running XOR hits k=6, we increment the count.

Algorithm

  1. Initialize count = 0
  2. For each starting index i from 0 to n-1:
    • Set xorVal = 0
    • For each ending index j from i to n-1:
      • Compute xorVal = xorVal ⊕ arr[j]
      • If xorVal equals k, increment count
  3. Return count

Code

#include <vector>
using namespace std;

class Solution {
public:
    int subarrayXor(vector<int>& arr, int k) {
        int n = arr.size();
        int count = 0;

        for (int i = 0; i < n; i++) {
            int xorVal = 0;
            for (int j = i; j < n; j++) {
                xorVal ^= arr[j];
                if (xorVal == k) {
                    count++;
                }
            }
        }

        return count;
    }
};
class Solution:
    def subarrayXor(self, arr: list[int], k: int) -> int:
        n = len(arr)
        count = 0

        for i in range(n):
            xor_val = 0
            for j in range(i, n):
                xor_val ^= arr[j]
                if xor_val == k:
                    count += 1

        return count
class Solution {
    public int subarrayXor(int[] arr, int k) {
        int n = arr.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            int xorVal = 0;
            for (int j = i; j < n; j++) {
                xorVal ^= arr[j];
                if (xorVal == k) {
                    count++;
                }
            }
        }

        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times and the inner loop runs up to n times for each starting index. The total number of subarray checks is n*(n+1)/2, which is O(n²). Each XOR operation and comparison is O(1).

Space Complexity: O(1)

We only use a few integer variables (count, xorVal, i, j). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force checks all O(n²) subarrays. With n up to 10^5, this results in roughly 5 × 10^9 operations — well beyond what can be processed within typical time limits.

The root problem is the same as in many subarray problems: for each starting index, we redundantly reprocess elements that were already part of previous subarrays. We do not leverage any relationship between subarrays that share a common prefix.

Key insight using XOR properties: XOR has a special property: if A ⊕ B = C, then A = C ⊕ B. This means if we know the prefix XOR up to index j (call it prefXOR_j) and we want to know whether any subarray ending at j has XOR equal to k, we need to find a previous prefix XOR value prefXOR_i such that prefXOR_i ⊕ prefXOR_j = k, which rearranges to prefXOR_i = prefXOR_j ⊕ k. A hash map storing the frequency of all previously seen prefix XOR values lets us answer this in O(1) time, reducing the total complexity to O(n).

Optimal Approach - Prefix XOR with Hash Map

Intuition

This approach draws on a powerful property of XOR: it is its own inverse. If you XOR a number with itself, you get zero. And if A ⊕ B = C, then you can recover A by computing C ⊕ B.

Imagine walking along the array and keeping a running XOR of everything you have seen — this is the prefix XOR. At each position j, the prefix XOR tells you the cumulative XOR of elements from the start up to j.

Now, if there exists an earlier position i where the prefix XOR was some value A, and the current prefix XOR is C, then the XOR of the subarray from i+1 to j is A ⊕ C (because XORing the two prefixes cancels out everything before i+1). We want this subarray XOR to equal k, so we need A ⊕ C = k, which means A = C ⊕ k.

So at each step, we compute needed = prefXOR ⊕ k and ask: "How many times have I previously seen a prefix XOR equal to needed?" A hash map tracking the frequency of each prefix XOR value answers this question in O(1).

There is also a direct case: if the prefix XOR itself equals k, it means the subarray from the very beginning to the current index has XOR = k. We handle this naturally by initializing the hash map with {0: 1}, meaning "before processing any element, the prefix XOR was 0, and it occurred once."

Step-by-Step Explanation

Let's trace through arr = [4, 2, 2, 6, 4], k = 6:

Step 1: Initialize prefXOR = 0, count = 0, freqMap = {0: 1}.
The seed {0: 1} represents the empty prefix (before any element), which has XOR value 0.

Step 2: Process arr[0] = 4.

  • prefXOR = 0 ⊕ 4 = 4
  • needed = prefXOR ⊕ k = 4 ⊕ 6 = 2
  • Is 2 in freqMap? No → count += 0.
  • Add prefXOR=4 to freqMap: {0: 1, 4: 1}

Step 3: Process arr[1] = 2.

  • prefXOR = 4 ⊕ 2 = 6
  • needed = 6 ⊕ 6 = 0
  • Is 0 in freqMap? YES, frequency = 1 → count += 1. count = 1.
    (This means subarray from index 0 to 1 has XOR = 6: [4, 2])
  • Add prefXOR=6: {0: 1, 4: 1, 6: 1}

Step 4: Process arr[2] = 2.

  • prefXOR = 6 ⊕ 2 = 4
  • needed = 4 ⊕ 6 = 2
  • Is 2 in freqMap? No → count += 0.
  • Update prefXOR=4: {0: 1, 4: 2, 6: 1}

Step 5: Process arr[3] = 6.

  • prefXOR = 4 ⊕ 6 = 2
  • needed = 2 ⊕ 6 = 4
  • Is 4 in freqMap? YES, frequency = 2 → count += 2. count = 3.
    (Two subarrays ending at index 3 have XOR=6: [4,2,2,6] starting after the prefix XOR=4 at index 0 and at index 2. Wait — let's verify: from index 1 to 3: 2⊕2⊕6=6 ✓, and from the start to index 3 is 4⊕2⊕2⊕6=2 which is not 6. Actually the two prefix XOR=4 occurrences were at index 0 and index 2. Subarray (0,3]: indices 1-3 = [2,2,6] → XOR=6 ✓. Subarray (2,3]: index 3 = [6] → XOR=6 ✓.)
  • Add prefXOR=2: {0: 1, 4: 2, 6: 1, 2: 1}

Step 6: Process arr[4] = 4.

  • prefXOR = 2 ⊕ 4 = 6
  • needed = 6 ⊕ 6 = 0
  • Is 0 in freqMap? YES, frequency = 1 → count += 1. count = 4.
    (Subarray from the start to index 4: [4,2,2,6,4] → XOR=6 ✓)
  • Update prefXOR=6: {0: 1, 4: 2, 6: 2, 2: 1}

Result: count = 4.

Prefix XOR + Hash Map — Counting Matching Subarrays in One Pass — Watch how we maintain a running prefix XOR and use a frequency map to instantly count how many subarrays ending at the current index have XOR equal to k.

Algorithm

  1. Initialize prefXOR = 0, count = 0
  2. Create a frequency hash map freqMap and insert {0: 1} (empty prefix)
  3. For each element arr[i]:
    • Update prefXOR = prefXOR ⊕ arr[i]
    • Compute needed = prefXOR ⊕ k
    • If needed exists in freqMap, add freqMap[needed] to count
    • Increment freqMap[prefXOR] by 1
  4. Return count

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarrayXor(vector<int>& arr, int k) {
        int n = arr.size();
        unordered_map<int, int> freqMap;
        int prefXOR = 0;
        int count = 0;

        // Seed: empty prefix has XOR value 0
        freqMap[0] = 1;

        for (int i = 0; i < n; i++) {
            prefXOR ^= arr[i];

            // How many previous prefixes have XOR = prefXOR ^ k?
            int needed = prefXOR ^ k;
            if (freqMap.find(needed) != freqMap.end()) {
                count += freqMap[needed];
            }

            // Record current prefix XOR
            freqMap[prefXOR]++;
        }

        return count;
    }
};
from collections import defaultdict

class Solution:
    def subarrayXor(self, arr: list[int], k: int) -> int:
        freq_map = defaultdict(int)
        freq_map[0] = 1  # seed: empty prefix
        pref_xor = 0
        count = 0

        for num in arr:
            pref_xor ^= num

            # Check how many previous prefixes satisfy the condition
            needed = pref_xor ^ k
            count += freq_map[needed]

            # Record current prefix XOR
            freq_map[pref_xor] += 1

        return count
import java.util.HashMap;

class Solution {
    public int subarrayXor(int[] arr, int k) {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        freqMap.put(0, 1); // seed: empty prefix
        int prefXOR = 0;
        int count = 0;

        for (int i = 0; i < arr.length; i++) {
            prefXOR ^= arr[i];

            // How many previous prefixes have XOR = prefXOR ^ k?
            int needed = prefXOR ^ k;
            count += freqMap.getOrDefault(needed, 0);

            // Record current prefix XOR
            freqMap.put(prefXOR, freqMap.getOrDefault(prefXOR, 0) + 1);
        }

        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once. At each step, we perform one XOR operation, one hash map lookup, and one hash map insertion or update — all O(1) on average. The total work is O(n).

Space Complexity: O(n)

In the worst case, every prefix XOR value is unique, so the hash map stores up to n+1 entries (including the seed). This requires O(n) additional space.