Parottasalna

Problem Statement

Geeks For Geeks: https://www.geeksforgeeks.org/problems/count-subarray-with-given-xor/1

Given an array of integers arr[] and a number k, count the number of subarrays having XOR of their elements as k.

Input: arr[] = [4, 2, 2, 6, 4], k = 6
Output: 4
Explanation: The subarrays having XOR of their elements as 6 are [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], and [6]. Hence, the answer is 4.

Input: arr[] = [5, 6, 7, 8, 9], k = 5
Output: 2
Explanation: The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]. Hence, the answer is 2.

My Approach

This problem is same as yesterday’s problem. Instead of sum, here its xor.

class Solution:
    def subarrayXor(self, arr, k):
        # code here
        n = len(arr)
        pre_xor_map = {}
        pre_xor = 0
        cnt = 0
    
        pre_xor_map[0] = 1
        for i in range(n):
            pre_xor = pre_xor ^ arr[i]
            remove = pre_xor ^ k
            cnt += pre_xor_map.get(remove, 0)
            pre_xor_map[pre_xor] = pre_xor_map.get(pre_xor, 0) + 1
    
        return cnt