Subarray with given XOR

  Given an array A[]  of size N of distinct positive integers and a number X, find the number of pairs of integers in the array whose XOR is equal to X.


Example 1:

Input: 
a = [4, 2, 2, 6, 4]
n = 5
x = 6
Output: 4
Explanation:The subarrays having XOR of their elements as 6 are:
 [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]


Example 2:

Input: 
 a = [5, 6, 7, 8, 9]
 n = 5
 x = 5
Output: 2
Explanation:  The subarrays having XOR of their elements as 2 are:
 [5] and [5, 6, 7, 8, 9]






c++ implementation:

int countPair(int n, int a[], int x)
    {
     int n=a.size();int s=0;
     unordered_map<int,int>m;
        int c=0;
        for(int i=0;i<n;i++)
        {
            s=s^a[i];

            if(s==x)
            c++;

            if(m.find(x^s)!=m.end())
            c=c+m[x^s];
            
            m[s]++;
        }
     return c;
    }
Time Complexity: O(n) 

space Complexity: O(n) 




 

darkmode