POTD #14 - Count Subarrays with given XOR | Geeks For Geeks

{% raw %}

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 = 6Output: 4Explanation: 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 = 5Output: 2Explanation: 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

{% endraw %}