[InterviewBit] Subarray with given XOR

Problem: Given an array of integers A and an integer B.

Find the total number of subarrays having bitwise XOR of all elements equals to B.

Example:

Input 1:

 A = [4, 2, 2, 6, 4]
 B = 6

Input 2:

 A = [5, 6, 7, 8, 9]
 B = 5

Example Output

Output 1:

 4

Output 2:

 2

Example Explanation

Explanation 1:

 The subarrays having XOR of their elements as 6 are:
 [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]

Explanation 2:

 The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]

Approach: We will use hash map to solve this problem. Approach is simple, we will keep doing the xor of every element and store each xor and its frequency in the hashmap. Now at every step we just need to check if curr_xor ^ B exist in the map or not, if yes we will just add count of curr_xor ^ B to the result. That's all!

Implementation in C#:

    public int solve(List<int> A, int B) 

    {

        int length = A?.Count ?? 0;

        if (length == 0)

        {

            return 0;

        }

        var xorMap = new Dictionary<int, int>();

        int xor = 0;

        int count = 0;

        xorMap[xor] = 1;

        for (int i = 0; i < length; ++i)

        {

            xor ^= A[i];

            if (xorMap.ContainsKey(B ^ xor))

            {

                count += xorMap[B ^ xor];

            }

            if (!xorMap.ContainsKey(xor))

            {

                xorMap[xor] = 0;

            }

            ++xorMap[xor];

        }

        return count;

    }

Complexity: O(n)