Coding Daily

Problem Description

Given an array of integers and a number k, count the number of subarrays whose XOR of elements equals k.

Example:

Input: arr[] = [4, 2, 2, 6, 4], k = 6
Output: 4
Explanation: The subarrays with XOR equal to 6 are:
- [4, 2]: 4 ^ 2 = 6
- [4, 2, 2, 6, 4]: 4 ^ 2 ^ 2 ^ 6 ^ 4 = 6
- [2, 2, 6]: 2 ^ 2 ^ 6 = 6
- [6]: 6 = 6

Solution Code

import java.util.HashMap;

class Solution {
    public long subarrayXor(int arr[], int k) {
        HashMap<Integer, Integer> xorMap = new HashMap<>(); // To store prefix XORs and their frequencies
        xorMap.put(0, 1); // Initialize with prefix XOR 0 occurring once
        int prefixXor = 0; // To store the running prefix XOR
        long count = 0; // To store the count of subarrays with XOR k

        for (int num : arr) {
            prefixXor ^= num; // Update the running prefix XOR

            // If (prefixXor ^ k) exists in the map, it means there are subarrays ending at the current index with XOR k
            if (xorMap.containsKey(prefixXor ^ k)) {
                count += xorMap.get(prefixXor ^ k);
            }

            // Update the frequency of the current prefix XOR in the map
            xorMap.put(prefixXor, xorMap.getOrDefault(prefixXor, 0) + 1);
        }

        return count;
    }
}

Hint

Use a hash map to store the frequency of prefix XORs. This helps in efficiently finding the number of subarrays that XOR to k.

Approach Name

Prefix XOR with Hash Map

Intuition

The idea is to use the concept of prefix XORs to determine the number of subarrays that XOR to k. By maintaining a running prefix XOR and storing the frequency of each prefix XOR in a hash map, we can efficiently check if a subarray with XOR k exists.

Algorithm

Initialize a hash map to store prefix XORs and their frequencies. Start by putting (0, 1) in the map to handle the case where the subarray starts from the beginning.
Initialize prefixXor to 0 and count to 0.
Iterate through the array:
- Update the prefixXor by XORing the current element.
- If (prefixXor ^ k) exists in the map, increment the count by the frequency of (prefixXor ^ k).
- Update the frequency of the current prefixXor in the map.
Return the count of subarrays with XOR k.

Test Input

4 2 2 6 4, 6

Complexity Analysis

Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once, and each lookup/insert operation in the hash map takes O(1) on average.
Space Complexity: O(n), as the hash map can store up to n prefix XORs in the worst case.

This solution efficiently counts the number of subarrays with XOR k using the prefix XOR approach and a hash map, ensuring optimal performance for the given constraints.

Count Subarrays with given XOR