Count Triplets That Can Form Two Arrays of Equal XOR Solution

Problem

Given an integer array, find the number of triplets (i, j, k) — where i < j ≤ k — such that XOR-ing elements from index i to j−1 produces the same value as XOR-ing elements from index j to k. In other words, you can split the subarray arr[i..k] at any interior point and have both halves XOR to the same value.

Input: arr = [2, 3, 1, 6, 7]
Output: 4
Explanation: (0,1,2), (0,2,2), (2,3,4), (2,4,4) — the subarrays [2,3,1] and [1,6,7] each XOR to zero, and each permits two distinct split points.

Intuition

If the left half a equals the right half b, then a XOR b = 0. That means the entire subarray arr[i..k] must XOR to zero. Once you find such a subarray, every split point j strictly between i and k produces a valid triplet — so a single zero-XOR subarray of length L contributes exactly L−1 triplets. The challenge reduces to efficiently counting zero-XOR subarrays and their lengths.

Approach 1 — Brute Force

Try every valid (i, j, k) combination, computing both XOR segments directly. Build xor_a and xor_b incrementally to keep the innermost loop O(1) per step rather than re-scanning from scratch.

Fix i and iterate j from i+1 to n−1, extending xor_a by one element each step.
For each j, iterate k from j to n−1, extending xor_b by one element each step.
When xor_a equals xor_b, increment the count.

1def countTriplets(arr: list[int]) -> int:
2    total = 0
3    n = len(arr)
4    for i in range(n):
5        xor_a = 0
6        for j in range(i + 1, n):
7            xor_a ^= arr[j - 1]       # extend left segment to cover arr[i..j-1]
8            xor_b = 0
9            for k in range(j, n):
10                xor_b ^= arr[k]        # extend right segment to cover arr[j..k]
11                if xor_a == xor_b:
12                    total += 1
13    return total

Time: O(n³) — three nested loops each up to n.
Space: O(1) — only scalar variables.

Approach 2 — Prefix XOR

Precompute a prefix XOR array so any subarray XOR is O(1). Then for each pair (i, k), check whether arr[i..k] XORs to zero in constant time. When it does, add (k − i) directly — no need to enumerate j.

Build prefix_xor where prefix_xor[i] = arr[0] XOR … XOR arr[i−1] (with prefix_xor[0] = 0).
XOR of arr[i..k] = prefix_xor[k+1] XOR prefix_xor[i].
When this equals zero, add (k − i) to the answer.

1def countTriplets(arr: list[int]) -> int:
2    n = len(arr)
3    prefix_xor = [0] * (n + 1)
4    for i in range(n):
5        prefix_xor[i + 1] = prefix_xor[i] ^ arr[i]
6
7    total = 0
8    for i in range(n):
9        for k in range(i + 1, n):
10            if prefix_xor[k + 1] ^ prefix_xor[i] == 0:
11                total += k - i    # every j in (i, k] is a valid split point
12    return total

Time: O(n²) — two nested loops after an O(n) precomputation pass.
Space: O(n) — the prefix XOR array.

Approach 3 — Hash Map (One Pass)

prefix_xor[k+1] == prefix_xor[i] means the subarray arr[i..k] XORs to zero. Instead of scanning all prior i for each k, a hash map records how many times each prefix XOR value has appeared and the sum of those positions. When the current prefix XOR matches a stored value, all prior matching positions contribute simultaneously in O(1).

Initialize the map with XOR value 0 appearing once at position 0 (the empty prefix).
At each index k, compute the running prefix XOR (which equals prefix_xor[k+1]).
If this XOR was seen before at positions p₁, p₂, …, add count × k − sum(pᵢ) to the answer — this is the sum of (k − pᵢ) over all prior matching positions.
Record the current prefix XOR at position k+1.

1def countTriplets(arr: list[int]) -> int:
2    total = 0
3    current_xor = 0
4    xor_freq: dict[int, int] = {0: 1}      # how many times each prefix XOR appeared
5    xor_index_sum: dict[int, int] = {0: 0} # sum of prefix-array positions for each XOR value
6
7    for k in range(len(arr)):
8        current_xor ^= arr[k]  # now equals prefix_xor[k+1]
9
10        if current_xor in xor_freq:
11            # sum of (k - p) for every prior position p = count*k - sum(p)
12            total += xor_freq[current_xor] * k - xor_index_sum[current_xor]
13
14        # record prefix_xor[k+1] appearing at prefix-array index k+1
15        xor_freq[current_xor] = xor_freq.get(current_xor, 0) + 1
16        xor_index_sum[current_xor] = xor_index_sum.get(current_xor, 0) + (k + 1)
17
18    return total

Time: O(n) — a single pass with O(1) hash map operations per step.
Space: O(n) — hash maps grow at most to n+1 entries.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n³)	O(1)	n ≤ 50, or when clarity matters more than speed
Prefix XOR	O(n²)	O(n)	n ≤ 1000, straightforward to implement and verify
Hash Map	O(n)	O(n)	n is large or optimal performance is required

Common Mistakes

Misplacing the segment boundary — a covers arr[i..j−1] and b covers arr[j..k]; shifting j by one (e.g., arr[i..j] and arr[j+1..k]) double-counts the element at j and produces wrong results even though the code looks plausible.
Looping over j after finding a zero-XOR subarray — once you know arr[i..k] XORs to zero, every interior j is valid. Iterating j to count them converts an O(1) step into O(n), pushing an O(n²) solution to O(n³).
Updating the hash map before reading it — in Approach 3, adding the current position to xor_freq before checking for matches would allow i = k, producing j from k+1 onward, which is out of the valid range for triplets.
Storing the wrong index in xor_index_sum — the stored value is k+1 (the prefix-array position), but the contribution formula subtracts it from k (the original array index). Storing k instead of k+1 shifts every contribution by 1 and produces a total that's off by the number of matched pairs.
Omitting the initial {0: 1} entry — without seeding the map at position 0, subarrays that start at index 0 and XOR to zero are never counted.

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