# C++ program to Count the number of subarrays having given XOR

In this tutorial, We will learn how to implement an efficient C++ program to count the number of subarrays having the given XOR.

Consider an array A[] and a given number B, We have to find the number of subarrays of A having XOR of its elements is equal to the given number B.

**Example:**

INPUT: A[] = { 5, 4, 5, 6, 8, 4, 2, 9 } , B = 6

OUTPUT : Count = 2

Explanation:

Subarrays having XOR of their elements as B are {6} and { 4, 2 }

INPUT: A[] = { 7, 5, 6, 2, 4, 2 } , B = 4

OUTPUT : Count = 4

Explanation:

Subarrays having XOR of their elements as B are {7, 5, 6}, {6, 2}, {2, 4, 2} and {4}

## Count the number of subarrays having given XOR in C++

The naive approach to solve this problem is by finding all the subarrays of the given array and calculating the XOR of their elements.

Time complexity for the above will be O (n^2).

An efficient way to solve the given problem is by using a map. This approach will scale down the Time Complexity to O(n).

- Declare an int count and initialize it as zero.
- Create a map to store the count of the prefixes which has a particular XOR value.
- Calculate XorArray (Prefix Array) which has the prefix xor-sum. Initialize the first element of XorArray as the first element of the array then calculate the prefix array.
- Traverse through XorArray:
- Find XOR of current prefix with B (given XOR value).
- If the XOR already exists in the map then there exists a subarray ending at position i with the given XOR value. Add count of all the subarrays.
- Check if the subarray has XOR as the given value (B) or not. If it’s equal, increment count.
- Add this XOR (XorArray[i]) to the map.

- Return count.

**Implementation of the above algorithm:**

#include <bits/stdc++.h> using namespace std; //Function to return the count of the subarray //with the given XOR value int XORsubarray(int A[], int n, int B) { //Declare an int count and initialize it as zero int count = 0; // Create a map to store the count of the //prefixes which has a particular XOR value unordered_map<int, int> m; //Calculate XorArray (Prefix Array) which has the prefix xor-sum int* XorArray = new int[n]; // Initialize first element of XorArray array XorArray[0] = A[0]; // Calculate the prefix array for (int i = 1; i < n; i++) XorArray[i] = XorArray[i - 1] ^ A[i]; // Traverse in the XorArray for (int i = 0; i < n; i++) { // Find XOR of current prefix int curr = B ^ XorArray[i]; // If above XOR already in the map, then there exist a subarray // ending at position i with the given XOR value // Add count of all the subarrays count = count + ((long long)m[curr]); // If the subarray has XOR as B, increment count if (XorArray[i] == B) count++; // Add this XOR to the map m[XorArray[i]]++; } // return total count return count; } int main() { int A[] = { 7, 5, 6, 2, 4, 2 }; int B = 4; int n = sizeof(A) / sizeof(A[0]); cout << "Count = "<< XORsubarray(A, n, B); return 0; }

**Output:**

Count = 4

Time Complexity: O(n)

Also, refer:

## Leave a Reply