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

Your email address will not be published. Required fields are marked *