Count Triplets That Can Form Two Arrays of Equal XOR

How it works

We can use prefix XOR to find subarrays with XOR equal to 0 in linear time. If prefix[i] == prefix[k+1], then the XOR from index i to k is 0. For each prefix value, we track how many times we have seen it and the sum of indices where it occurred. When we see the same prefix again at index k, the contribution to the result is k * count - sum_of_indices, where count is how many times this prefix appeared before, and the formula accounts for all k - i values.

Steps

1. Initialize res and prefix to 0.
2. Create two hash maps: count to store frequency of each prefix value, and index_sum to store sum of indices for each prefix value.
3. Initialize count[0] = 1 to handle subarrays starting from index 0.
4. For each index i from 0 to N-1:
   • Update prefix by XORing it with arr[i].
   • If this prefix value has been seen before, add i * count[prefix] - index_sum[prefix] to res.
   • Increment count[prefix] by 1.
   • Add i + 1 to index_sum[prefix].
5. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Misunderstanding the Triplet Count Formula

When the XOR from index i to k equals zero, beginners often count it as just 1 triplet. However, j can be placed at any position from i+1 to k, yielding k - i valid triplets for each such pair.

Off-by-One Errors in Index Sum Tracking

In the optimal solution, the index sum needs to track i + 1 (not i) because we want the sum of starting positions for subarrays, and the formula i * count - index_sum requires this offset. Using just i leads to incorrect results.

Forgetting to Initialize count[0] = 1

The prefix XOR of 0 needs to be pre-initialized to handle subarrays starting from index 0. Without this initialization, valid triplets where the XOR from index 0 to some k equals zero will be missed.

from typing import List
from collections import defaultdict

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        N = len(arr)
        res = prefix = 0
        count = defaultdict(int)  # number of prefixes
        index_sum = defaultdict(int)  # sum of indices with that prefix
        count[0] = 1

        for i in range(N):
            prefix ^= arr[i]
            if prefix in count:
                res += i * count[prefix] - index_sum[prefix]
            count[prefix] += 1
            index_sum[prefix] += i + 1

        return res

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int N = arr.size(), res = 0, prefix = 0;
        unordered_map<int, int> count; // number of prefixes
        unordered_map<int, int> indexSum; // sum of indices with that prefix
        count[0] = 1;

        for (int i = 0; i < N; i++) {
            prefix ^= arr[i];
            if (count.count(prefix)) {
                res += i * count[prefix] - indexSum[prefix];
            }
            count[prefix]++;
            indexSum[prefix] += i + 1;
        }

        return res;
    }
};