Solution: Count Triplets That Can Form Two Arrays of Equal XOR

Statement

Given an array of integers, arr, we need to find three indices, i, j, and k, such that $0\leq$ i $<$ j $\leq$ k $<$ arr.length.

We define two values, a and b, as follows:

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]

• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note: ^ denotes the bitwise XOR operation.

Return the count of triplets (i, j, k) for which a is equal to b.

Constraints:

• $1 \leq$ arr.length $\leq 300$

• $1 \leq$ arr[i] $\leq 1000$

Solution

The naive approach to solve this problem is to exhaustively iterate through every possible triplet (i, j, k) and check if the XOR of the subarrays (i, j-1) and (j, k) is equal. This approach has a time complexity of $O(n^3)$ and a space complexity of $O(1)$, which makes it impractical for large arrays.

We use the prefix XOR approach to optimize the algorithm. For each index, we compute the XOR of all elements from the start of the array up to that index. We then iterate through all pairs of indices (start, end) and use the property that if the prefix XOR at two indices is equal, the XOR of the elements between them is zero. The number of valid triplets for each pair is calculated as end−start−1, and we update the result counter accordingly. This approach reduces the time complexity to $O(n^2)$. Its space complexity is $O(n)$, which is due to the space occupied by the prefix XOR array.

We can optimize the solution by maintaining a running prefix XOR instead of precomputing the prefix XOR values. The running prefix stores the XOR of all elements up to the current index i. We update it dynamically as we iterate through the array: