874827. Count Subarrays with given XOR
Count Subarrays with given XOR
Slug: count-subarray-with-given-xor
Difficulty: Medium
Id: 874827
Topic Tags: Arrays, Map
Company Tags: None
Summary
The problem asks to find the number of subarrays in an array that have a given XOR value. The input array contains binary values (0s and 1s), and the goal is to count the number of subarrays whose elements' XOR equals the target value.
Detailed Explanation
To solve this problem, we can use a hashmap to keep track of the cumulative XOR sum at each position in the array. We iterate through the array, calculating the cumulative XOR at each step. For each element, we check if the difference between the current cumulative XOR and the given XOR is present in our hashmap. If it is, that means we've found a subarray with the given XOR value, so we increment our count.
Here's a step-by-step breakdown of the solution:
- Initialize an empty hashmap
cumulative_xor_mapto store the cumulative XOR sums. - Iterate through the array, starting from the first element:
- Calculate the cumulative XOR sum at each position by XORing the current element with the previous cumulative XOR sum (or 0 if it's the first element).
- Store the cumulative XOR sum in
cumulative_xor_map.
- For each element in the array:
- Calculate the difference between the current cumulative XOR and the given XOR.
- Check if this difference is present in
cumulative_xor_map. If it is, increment our count of subarrays with the given XOR.
The time complexity of this solution is O(n), where n is the length of the input array. The space complexity is also O(n) due to the hashmap.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class CountSubarrays {
public static int countSubarrays(int[] arr, int targetXOR) {
Map<Integer, Integer> cumulative_xor_map = new HashMap<>();
int cumulative_xor_sum = 0;
int count = 0;
for (int i : arr) {
cumulative_xor_sum ^= i;
if (cumulative_xor_map.containsKey(cumulative_xor_sum ^ targetXOR)) {
count += cumulative_xor_map.get(cumulative_xor_sum ^ targetXOR);
}
cumulative_xor_map.put(cumulative_xor_sum, cumulative_xor_map.getOrDefault(cumulative_xor_sum, 0) + 1);
}
return count;
}
}