# Count subarrays with given XOR

Posted in

Vinay Khatri
Last updated on August 10, 2024

## Problem

Given an array of integers, count the number of subarrays that have the XOR equal to ‘ x’.

#### Sample Input

`[4, 2, 2, 6, 4]  ‘x’ = 6`

`4`

#### Explanation

[4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6] are the subarrays with XOR equal to 6

## Approach

We can use hashmaps and prefix arrays to solve this problem. We first store the XOR of all the prefixes of the array in a separate array data structure. Create a map data structure to store the count of prefixes having given XOR value. Let xorArray store the XOR all prefixes of the input array.

The intuition behind the approach is that if we are at current index j+1 , and xorArray[i]...xorArray[j] has the XOR value equal to ‘x’ , then xorArray[0]...xorArray[i-1] must be present in the prefix array, and the value should be equal to xorArray[j+1]^x We can use the below algorithm to solve this problem Traverse the array and for each element arr[i]:

1. If the x^xorArray[i] is present in the map, increment the count of the answer with the value of the XOR
2. If the current prefix is already on the map, increment the answer by 1
3. At last, increment the current prefix’s value in the map by 1.

### Complexity Analysis

The time complexity is O(N), and the space complexity is also O(N) due to the map

#### C++ Programming

```#include <bits/stdc++.h>
using namespace std;

long long solve(int arr[], int n, int x)
{
long long ans = 0;

int* xorArr = new int[n];

unordered_map<int, int> mp;

// Initialize first element of prefix array
xorArr[0] = arr[0];

// Computing the prefix array.
for (int i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];

// traverse the array
for (int i = 0; i < n; i++) {
// Find XOR of current prefix with x.
int tmp = x ^ xorArr[i];

// if the value of 'tmp' exists in map
ans = ans + ((long long)mp[tmp]);

// If this subarray has XOR equal to x itself.
if (xorArr[i] == x)
ans++;

mp[xorArr[i]]++;
}

return ans;
}

int main()
{
int arr[] = { 4, 2, 2, 6, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 6;
cout << solve(arr, n, x);

return 0;
}```

`4`

#### Java Programming

```import java.util.*;

class Solution {
static long solve(int arr[], int n, int x)
{
long ans = 0; // Initialize answer to be returned

// to store prefixes XOR
int[] xorArr = new int[n];

HashMap<Integer, Integer> mp  = new HashMap<Integer, Integer>();

// Initialize first element of prefix array
xorArr[0] = arr[0];

// Computing the prefix array.
for (int i = 1; i < n; i++)
xorArr[i] = xorArr[i - 1] ^ arr[i];

// traverse the array
for (int i = 0; i < n; i++) {
// Find XOR of current prefix with x.
int tmp = x ^ xorArr[i];

// if the value if 'tmp' exists in the map
ans = ans+ (mp.containsKey(tmp) == false? 0:((long)mp.get(tmp)));

// If this subarray has XOR equal to x itself.
if (xorArr[i] == x)
ans++;

if (mp.containsKey(xorArr[i]))
mp.put(xorArr[i], mp.get(xorArr[i]) + 1);
else
mp.put(xorArr[i], 1);
}

return ans;
}

public static void main(String[] args)
{
int arr[] = { 4, 2, 2, 6, 4 };
int n = arr.length;
int x = 6;

System.out.print(solve(arr, n, x));
}
}```

`4`

#### Python Programming

```def solve(arr, n, x):
ans = 0 # Initialize answer

# prefix array
xorArr =[0 for _ in range(n)]

mp = dict()

# Initialize first element
# of prefix array
xorArr[0] = arr[0]

# Computing the prefix array.
for i in range(1, n):
xorArr[i] = xorArr[i - 1] ^ arr[i]

# traverse the array
for i in range(n):
# Find XOR of current prefix with x.
tmp = x ^ xorArr[i]

# if the value of 'tmp' exists in the array
if tmp in mp.keys():
ans = ans + (mp[tmp])

if (xorArr[i] == x):
ans += 1

mp[xorArr[i]] = mp.get(xorArr[i], 0) + 1

return ans

arr = [4, 2, 2, 6, 4]
n = len(arr)
x = 6

print(solve(arr, n, x))```

`4`