Subarrays With Given XOR Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/subarray-with-xor

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A and target value, find the number of subarrays whose XOR is equal to the target value.

Naive Approach

The simple solution is to calculate the XOR of all the subarrays of the given array and count the number of subarrays whose XOR is equal to the target.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int numSubarrayWithXOR(vector<int> &A, int target) {
    int n = A.size();
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int subarrayXor = 0;
		for (int j = i; j < n; j++) {
			subarrayXor ^= A[j];
			if (subarrayXor == target) {
				ans++;
			}
		}
	}
	return ans;
}

Java

class Solution {
	int numSubarrayWithXOR(int[] A, int target) {
	    int n = A.length;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int subarrayXor = 0;
			for (int j = i; j < n; j++) {
				subarrayXor ^= A[j];
				if (subarrayXor == target) {
					ans++;
				}
			}
		}
		return ans;
	}
}

Optimal Approach

Let for an index i, Xi denotes XOR of elements from the index 0 to i and Xj denotes XOR of elements from the index 0 to j  

(i < j).

Then Xi ^ Xj will give us the XOR of all the elements from the index i +1 to j and if Xi ^ Xj = target then we will get a subarray whose XOR is equal to target. Also if Xi ^ Xj = target then  Xj ^ target = Xi.

This idea can be used to solve the problem efficiently with the help of a hashmap.

• Initialize an empty hashmap say CountOfPrefixXor to store the count of all the prefix xor.
• Initialize a variable prefixXor to 0.
• Traverse the given array and for every index i update the prefixXor . If the prefixXor equals the target then increment the answer by 1. If prefixXor ^ target is present in the hashmap then add its count in the answer. Store the current prefixXor in the hashmap.
• Finally, return the answer.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int numSubarrayWithXOR(vector<int> &A, int target) {
    int n = A.size();
	int ans = 0;
	int prefixXor = 0;
	unordered_map<int, int> countOfPrefixXor;
	for (int i = 0; i < n; i++) {
		prefixXor ^= A[i];
		if (prefixXor == target) {
			ans++;
		}
		if (countOfPrefixXor[prefixXor ^ target] != 0) {
			ans += countOfPrefixXor[prefixXor ^ target];
		}
		countOfPrefixXor[prefixXor]++;
	}
	return ans;
}

Java

class Solution {
	int numSubarrayWithXOR(int[] A, int target) {
	    int n = A.length;
		int ans = 0;
		int prefixXor = 0;
		HashMap<Integer, Integer> countOfPrefixXor = new HashMap<Integer, Integer> ();
		for (int i = 0; i < n; i++) {
			prefixXor ^= A[i];
			if (prefixXor == target) {
				ans++;
			}
			if (countOfPrefixXor.get(prefixXor ^ target) != null) {
				ans += countOfPrefixXor.get(prefixXor ^ target);
			}
			if (countOfPrefixXor.get(prefixXor) != null) {
                countOfPrefixXor.put(prefixXor, countOfPrefixXor.get(prefixXor) + 1);
			} else {
                countOfPrefixXor.put(prefixXor, 1);
			}
		}
		return ans;
	}
}