03. Count Subarrays with Given XOR

The problem can be found at the following link: Problem Link

Problem Description

Given an array of integers arr[] and an integer k, count the number of subarrays whose XOR is equal to k.

Examples

Example 1

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

Explanation: The subarrays having XOR of their elements as 6 are:

1. [4, 2]

2. [4, 2, 2, 6, 4]

3. [2, 2, 6]

4. [6]

Hence, the output is 4.

Example 2

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

Explanation: The subarrays having XOR of their elements as 5 are:

1. [5]

2. [5, 6, 7, 8, 9]

Hence, the output is 2.

Constraints

• $1 ≤ arr.size() ≤ 10^5$

• $0 ≤ arr[i] ≤ 10^5$

• $0 ≤ k ≤ 10^5$

My Approach

The problem is solved using the Prefix XOR technique combined with a Hash Map for efficient subarray counting.

1. Key Observations:

   • Let XOR(A, B) represent the XOR of elements in subarray [A...B].

   • If the XOR of a subarray [i...j] equals k, then: $( \text{XOR(0, i-1)} \oplus \text{XOR(0, j)} = k )$. Rearranging gives: $( \text{XOR(0, i-1)} = \text{XOR(0, j)} \oplus k )$.

2. Algorithm Steps:

   • Traverse the array while maintaining a Prefix XOR (prefXOR) of all elements encountered so far.

   • Use a hash map to store the frequency of each prefXOR value encountered.

   • For each element, calculate: $( \text{TargetXOR} = \text{prefXOR} \oplus k )$. If TargetXOR exists in the hash map, it means there are subarrays ending at the current index whose XOR equals k.

   • Add these counts to the result.

   • Finally, update the hash map with the current prefXOR.

Time and Auxiliary Space Complexity

• Expected Time Complexity: $( O(n) )$, where n is the size of the array. We traverse the array once, and each hash map operation (insertion or lookup) takes $( O(1) )$ on average.

• Expected Auxiliary Space Complexity: $( O(n) )$, as we store up to n unique prefXOR values in the hash map.

Code (C++)

class Solution {
public:
    long subarrayXor(vector<int> &arr, int k) {
        long res = 0, prefXOR = 0;
        unordered_map<int, int> mp;
        for (int val : arr) {
            prefXOR ^= val;
            res += mp[prefXOR ^ k] + (prefXOR == k);
            mp[prefXOR]++;
        }
        return res;
    }
};

Code (Java)

class Solution {
    public long subarrayXor(int[] arr, int k) {
        long res = 0, prefXOR = 0;
        Map<Long, Integer> mp = new HashMap<>();
        mp.put(0L, 1);
        for (int val : arr) {
            prefXOR ^= val;
            res += mp.getOrDefault(prefXOR ^ k, 0);
            mp.put(prefXOR, mp.getOrDefault(prefXOR, 0) + 1);
        }

        return res;
    }
}

Code (Python)

class Solution:
    def subarrayXor(self, arr, k):
        res, prefXOR = 0, 0
        count = {0: 1}
        for val in arr:
            prefXOR ^= val
            res += count.get(prefXOR ^ k, 0)
            count[prefXOR] = count.get(prefXOR, 0) + 1
        return res

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count