Count Subarrays with given XOR

Given an array of integers arr[] and a number k, count the number of subarrays having XOR of their elements as k.

Examples: 

Input: arr[] = [4, 2, 2, 6, 4], k = 6
Output: 4
Explanation: The subarrays having XOR of their elements as 6 are [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], and [6]. Hence, the answer is 4.

Input: arr[] = [5, 6, 7, 8, 9], k = 5
Output: 2
Explanation: The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]. Hence, the answer is 2.

Input: arr[] = [1, 1, 1, 1], k = 0
Output: 4
Explanation: The subarrays are [1, 1], [1, 1], [1, 1] and [1, 1, 1, 1].

Constraints:

• 1 ≤ arr.size() ≤ 10⁵
• 0 ≤ arr[i] ≤10⁵
• 0 ≤ k ≤ 10⁵

Approach 01:

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

class Solution {
public:
    int subarrayXor(vector<int>& nums, int targetXor) {
        int n = nums.size();
        int subarrayCount = 0;
        int currentXorSum = 0;
        unordered_map<int, int> xorSumFrequency;

        // Initialize the map with 0 XOR sum having frequency 1
        xorSumFrequency[0] = 1;

        for (int num : nums) {
            currentXorSum ^= num;  // Calculate XOR sum up to current element

            // Check if there exists a subarray with XOR equal to targetXor
            if (xorSumFrequency.find(currentXorSum ^ targetXor) != xorSumFrequency.end()) {
                subarrayCount += xorSumFrequency[currentXorSum ^ targetXor];
            }

            // Update the frequency of the current XOR sum
            xorSumFrequency[currentXorSum]++;
        }

        return subarrayCount;
    }
};

from typing import List
from collections import defaultdict

class Solution:
    def subarrayXor(self, arr: List[int], targetXor: int) -> int:
        n = len(arr)
        subarrayCount = 0
        currentXorSum = 0
        xorSumFrequency = defaultdict(int)

        # Initialize the dictionary with XOR sum 0 having frequency 1
        xorSumFrequency[0] = 1

        for num in arr:
            currentXorSum ^= num  # Calculate XOR sum up to current element

            # Check if there exists a subarray with XOR equal to targetXor
            if currentXorSum ^ targetXor in xorSumFrequency:
                subarrayCount += xorSumFrequency[currentXorSum ^ targetXor]

            # Update the frequency of the current XOR sum
            xorSumFrequency[currentXorSum] += 1

        return subarrayCount

Time Complexity:

• Loop Over Array:
  • We iterate over the array of numbers once.
  • For each element, the XOR operation is \( O(1) \), and checking the map is also \( O(1) \) on average.
  • Thus, this step has a time complexity of \( O(n) \), where \( n \) is the size of the input array nums.
• Overall Time Complexity:

  \( O(n) \), where \( n \) is the size of nums.

Space Complexity:

• Frequency Map:
  • The unordered map stores the frequency of XOR sums.
  • In the worst case, the map stores up to \( O(n) \) unique XOR sums, where \( n \) is the size of nums.
• Auxiliary Variables:
  • The auxiliary variables (currentXorSum, subarrayCount, and n) use \( O(1) \) space.
• Overall Space Complexity:

  \( O(n) \), dominated by the space used by the frequency map.