Count Triplets That Can Form Two Arrays of Equal XOR

LeetCode Count Triplets That Can Form Two Arrays of Equal XOR (Problem 1442) asks you to find triplets (i, j, k) in an integer array where the XOR of one subarray equals the XOR of another. The brute force solution checks every possible triplet in O(n^3), but a single insight about XOR cancellation brings this down to O(n) with a hash map.

The problem

Given an integer array arr, define:

• a = arr[i] XOR arr[i+1] XOR ... XOR arr[j-1]
• b = arr[j] XOR arr[j+1] XOR ... XOR arr[k]

Return the number of triplets (i, j, k) where 0 <= i < j <= k < n and a == b.

arr = [2, 3, 1, 6, 7]  ->  4
arr = [1, 1, 1, 1, 1]  ->  10

The approach

The key insight is that if a == b, then a XOR b = 0. Since a XOR b is the XOR of the entire range from index i to index k, the condition a == b is equivalent to arr[i] XOR arr[i+1] XOR ... XOR arr[k] = 0.

This means you do not actually need to find j. If the XOR of the range [i..k] is zero, then every choice of j between i+1 and k (inclusive) creates a valid triplet. That gives you k - i valid triplets for each such range.

Now bring in prefix XOR. Define prefix[0] = 0 and prefix[m] = arr[0] XOR arr[1] XOR ... XOR arr[m-1]. The XOR of the range [i..k] equals prefix[i] XOR prefix[k+1]. So the XOR of [i..k] is zero exactly when prefix[i] = prefix[k+1].

For each position k, you need to find all earlier positions i where prefix[i] = prefix[k+1], and sum up (k - i) across all of them. You can do this efficiently with two hash maps: one tracking how many times each prefix XOR value has appeared (count), and one tracking the sum of all indices where each value appeared (index_sum). The total triplets contributed by position k is count * k - index_sum.

Step-by-step walkthrough

The code

def count_triplets(arr):
    n = len(arr)
    count = 0
    prefix_xor = 0
    xor_count = {0: 1}
    xor_index_sum = {0: 0}

    for k in range(n):
        prefix_xor ^= arr[k]

        if prefix_xor in xor_count:
            count += xor_count[prefix_xor] * k - xor_index_sum[prefix_xor]

        xor_count[prefix_xor] = xor_count.get(prefix_xor, 0) + 1
        xor_index_sum[prefix_xor] = xor_index_sum.get(prefix_xor, 0) + (k + 1)

    return count

Here is how the code works:

1. Maintain a running prefix XOR. For each index k, compute the XOR of all elements from index 0 through k. This is prefix[k+1] in the mathematical formulation.

2. Check the maps before updating. If the current prefix XOR has appeared before, those earlier positions are potential values of i. The number of triplets is count_of_matches * k - sum_of_indices. This formula works because each matching position i contributes k - i triplets (one for each valid j), and summing k - i over all matches gives count * k - index_sum.

3. Update the maps. Record the current position (using k+1 as the stored index, since prefix XOR at position k corresponds to index k+1 in the prefix array) and increment the count for this XOR value.

4. Seed with {0: count=1, index_sum=0}. Before any elements are processed, the prefix XOR is 0 at the "virtual" position 0. This lets you catch ranges that start from the very beginning of the array.

Complexity analysis

Time: O(n). You iterate through the array once. Each hash map lookup and update is O(1) on average.

Space: O(n). The two hash maps store at most n + 1 entries each (one for each distinct prefix XOR value).

The building blocks

XOR cancellation

The core insight that a XOR b = 0 implies a = b. This property lets you replace the condition "two subarrays have equal XOR" with the simpler condition "the XOR of the entire range is zero." Recognizing when XOR cancellation applies is a skill that shows up repeatedly in bit manipulation problems.

Prefix XOR + hash map

Just as prefix sums let you compute the sum of any subarray in O(1), prefix XOR lets you compute the XOR of any subarray in O(1). Combined with a hash map to track previous prefix XOR values, you can find all ranges with a target XOR value in linear time. The mechanics are nearly identical to the prefix sum + hash map pattern used in Subarray Sum Equals K.

Counting with index sums

A subtle but important detail: when each matching position contributes a different number of triplets (k - i), you cannot just count matches. You need the sum of stored indices too. Storing both count and index_sum in the hash map lets you compute the total contribution in O(1) per position.

Edge cases

• All elements identical and non-zero. For example, arr = [5, 5, 5]. The prefix XOR alternates between 0 and 5, so only pairs with even-length ranges produce XOR of zero.
• All elements are zero. Every subarray XOR is zero, so every valid triplet (i, j, k) with i < j <= k is counted. The answer is n * (n - 1) * (n - 2) / 6 for an array of n zeros... but only when computed by the formula. The hash map handles this naturally.
• Single or two elements. You need at least two elements (since i < j <= k requires k >= 1). With fewer than two elements, the answer is 0. The algorithm returns 0 because no valid range can produce a match.
• Large XOR values. XOR operates on the full bit width of integers. The hash map handles arbitrarily large keys, so no overflow concerns arise in Python.

From understanding to recall

The insight that a = b means XOR(i..k) = 0 is the conceptual leap. Once you have that, the problem reduces to a familiar prefix + hash map pattern. But the counting formula, count * k - index_sum, is easy to get wrong under pressure. You might forget to track index sums, or mix up whether to store k or k+1.

Spaced repetition locks in these details. You practice writing the two-map solution from scratch, catching the seeding step and the index arithmetic each time. After a few reps, the formula becomes automatic and you can focus on recognizing the XOR cancellation opportunity in new problems.

Related posts

• Single Number - The simplest XOR cancellation problem, where pairs cancel and the lone element survives
• XOR Cancellation Pattern - A deep dive into the XOR properties that power this problem, including commutativity, associativity, and self-cancellation
• Subarray Sum Equals K - The prefix sum + hash map pattern that this problem adapts for XOR instead of addition