Count Triplets That Can Form Two Arrays of Equal XOR

Count Triplets That Can Form Two Arrays of Equal XOR

What is this problem about?

The Count Triplets That Can Form Two Arrays of Equal XOR coding problem involves an array of integers. You need to find the number of triplets $(i, j, k)$ such that $0 \le i < j \le k < n$, where the XOR sum of the segment $[i, j-1]$ equals the XOR sum of the segment $[j, k]$.

Why is this asked in interviews?

This "Medium" problem is used by Meta and Google to test knowledge of bit manipulation and the prefix sum interview pattern. The key insight is that if $XOR(i \dots j-1) == XOR(j \dots k)$, then the total XOR sum of the entire range $XOR(i \dots k)$ must be zero (because $A \oplus A = 0$). This reduces the problem from finding triplets to finding any range with a zero XOR sum.

Algorithmic pattern used

The problem uses Prefix XOR and a Hash Table.

1. Insight: If $XOR(i \dots k) = 0$, any index $j$ such that $i < j \le k$ will satisfy the condition. There are $k - i$ such possible values for $j$.
2. Algorithm:
   • Maintain a running XOR sum prefix_xor.
   • Store the frequency and the sum of indices for each prefix_xor value in a Hash Map.
   • For every zero XOR range found (where the current prefix_xor matches a previous one), add the contribution to the result.
   • Contribution = (count * current_index) - (sum_of_previous_indices) - count.

Example explanation

arr = [2, 3, 1]

1. prefix_xor starts at 0. Map: {0: [count:1, sum: -1]} (using -1 for the initial state).
2. Index 0: prefix_xor = 2. Map: {0: [1, -1], 2: [1, 0]}.
3. Index 1: prefix_xor = 2 ^ 3 = 1. Map: {..., 1: [1, 1]}.
4. Index 2: prefix_xor = 1 ^ 1 = 0.
   • We saw prefix_xor = 0 at virtual index -1.
   • Range is $[-1+1, 2]$, which is $[0, 2]$.
   • Elements: [2, 3, 1]. Total XOR = $2 \oplus 3 \oplus 1 = 0$.
   • Triplets: $(0, 1, 2)$ and $(0, 2, 2)$. Count = 2.

Common mistakes candidates make

• Triplet Search: Trying to iterate through all $i, j, k$, which is $O(N^3)$.
• Missing the 0-case: Forgetting that if the prefix XOR itself is 0, it forms a range starting from the very beginning of the array.
• Index math: Getting the $k-i$ contribution formula wrong.

Interview preparation tip

In XOR problems, the property $A \oplus B = C \implies A \oplus C = B$ is king. Combining this with prefix sums allows you to find target segments in linear time, much like the "Subarray Sum Equals K" problem.