cyberangles blog

Count Subarrays with Given XOR

In the realm of competitive programming and data structures, problems related to subarray operations are quite common. One such interesting problem is to count the number of subarrays in a given array whose XOR (exclusive - or) value is equal to a given number. The XOR operation is a bit - level operation that returns 1 if the two bits being compared are different and 0 if they are the same. This problem can be solved using various techniques, and in this blog, we will explore an efficient approach using a hash map.

2026-07

Table of Contents#

  1. Problem Statement
  2. Naive Approach
  3. Efficient Approach using Hash Map
  4. Common Practices
  5. Best Practices
  6. Example Usage
  7. Conclusion
  8. References

Problem Statement#

Given an array arr of integers and an integer k, the goal is to find the number of non - empty subarrays of arr such that the XOR of all the elements in the subarray is equal to k.

For example, if arr = [4, 2, 2, 6, 4] and k = 6, the subarrays [4, 2], [2, 2, 6], [6] have XOR values equal to 6, so the answer is 3.

Naive Approach#

Explanation#

The naive approach involves generating all possible subarrays of the given array and calculating the XOR of each subarray. For each subarray, we check if the XOR value is equal to the given number k. If it is, we increment a counter.

Code in Python#

def count_subarrays_naive(arr, k):
    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
 
arr = [4, 2, 2, 6, 4]
k = 6
print(count_subarrays_naive(arr, k))

Time and Space Complexity#

  • Time Complexity: The time complexity of this approach is $O(n^2)$ because we have two nested loops to generate all possible subarrays.
  • Space Complexity: The space complexity is $O(1)$ because we are only using a constant amount of extra space.

Efficient Approach using Hash Map#

Explanation#

Let the XOR of elements from index 0 to i be x. If there exists an index j (j < i) such that the XOR of elements from index 0 to j is x ^ k, then the XOR of elements from index j + 1 to i is k.

We can use a hash map to store the frequency of the XOR values encountered so far. As we iterate through the array, we calculate the current XOR value. If current_xor ^ k is present in the hash map, we add its frequency to the count. Then we update the frequency of the current XOR value in the hash map.

Code in Python#

def count_subarrays(arr, k):
    n = len(arr)
    count = 0
    current_xor = 0
    xor_freq = {0: 1}  # Initialize with XOR 0 having frequency 1
    for i in range(n):
        current_xor ^= arr[i]
        if current_xor ^ k in xor_freq:
            count += xor_freq[current_xor ^ k]
        if current_xor in xor_freq:
            xor_freq[current_xor] += 1
        else:
            xor_freq[current_xor] = 1
    return count
 
arr = [4, 2, 2, 6, 4]
k = 6
print(count_subarrays(arr, k))

Time and Space Complexity#

  • Time Complexity: The time complexity of this approach is $O(n)$ because we are iterating through the array only once.
  • Space Complexity: The space complexity is $O(n)$ in the worst case because the hash map can store at most n distinct XOR values.

Common Practices#

  • Initializing the Hash Map: Always initialize the hash map with {0: 1}. This is because when the current XOR value is equal to k, we need to account for the subarray starting from index 0.
  • Iterating through the Array: Use a single loop to iterate through the array and calculate the current XOR value at each step.

Best Practices#

  • Using Appropriate Data Structures: For counting frequencies, a hash map (dictionary in Python) is a very efficient data structure as it provides $O(1)$ average - case access time.
  • Avoiding Redundant Calculations: Instead of calculating the XOR of each subarray from scratch, use the property of XOR to calculate the XOR of a subarray based on the XOR values of prefix subarrays.

Example Usage#

Let's consider another example. Suppose we have an array arr = [1, 2, 3, 4] and k = 3.

arr = [1, 2, 3, 4]
k = 3
print(count_subarrays(arr, k))

In this case, the subarrays [1, 2] and [3] have XOR values equal to 3. The count_subarrays function will correctly calculate the number of such subarrays.

Conclusion#

The problem of counting subarrays with a given XOR can be solved naively in $O(n^2)$ time, but an efficient approach using a hash map can reduce the time complexity to $O(n)$. By using the properties of XOR and appropriate data structures, we can solve this problem in an optimal way.

References#