C++ Solution using unordered_map and prefix_xor


#1

~Alogorithm : PREFIX 

    => Simply think it as a sum problem -> count the number of subarray having sum = k (target)

    1) We will maintain prefix_xor 

        1.1) and keep checking if the current value of prefix_xor == target or not //=> if yes , increase the count .

        1.2) Also, check how many prefix_xor values we have ‘encountered earlier’ having prefix_xor value as = current prefix_xor ^ target.

            and increase the count by jitni bari vo prefix encounter hua hai !  //=> count+=map[prefix_xor ^ target]

        1.3) Now just increase the count of map[prefix_xor]. Indicating that this value of prefix_xor has been encounterd earlier this many times

int subarray_xor(vector<int> &arr, int target)
{
int count = 0;
int prefix_xor = 0;          //It will store prefix xor ,(xor from 1st element to current elemen)
unordered_map<int, int> map; //It will maintain the count of the particular xor

for (int ele : arr)
{
    prefix_xor = prefix_xor ^ ele;
    if (prefix_xor == target)
        count++;
    count += map[prefix_xor ^ target];
    map[prefix_xor]++;
}

return count;
}