# Count Triplets That Can Form Two Arrays of Equal XOR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor)
Canonical: https://scaleengineer.com/dsa/problems/count-triplets-that-can-form-two-arrays-of-equal-xor
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
Given an array of integers `arr`.

We want to select three indices `i`, `j` and `k` where `(0 <= i < j <= k < arr.length)`.

Let's define `a` and `b` as follows:

* `a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]`
* `b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]`

Note that **^** denotes the **bitwise-xor** operation.

Return _the number of triplets_ (`i`, `j` and `k`) Where `a == b`.

**Example 1:**

**Input:** arr = [2,3,1,6,7]
**Output:** 4
**Explanation:** The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

**Example 2:**

**Input:** arr = [1,1,1,1,1]
**Output:** 10

**Constraints:**

* `1 <= arr.length <= 300`
* `1 <= arr[i] <= 108`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It iterates through all possible combinations of indices `i`, `j`, and `k` that satisfy the condition `0 <= i < j <= k < arr.length`. For each triplet, it calculates the XOR sums `a` (for subarray `arr[i...j-1]`) and `b` (for subarray `arr[j...k]`) and checks if they are equal. If they are, a counter is incremented.
**Time:** O(N^3), where N is the length of the array. The three nested loops for `i`, `j`, and `k` are the dominant factor in the runtime. · **Space:** O(1), as we only use a constant amount of extra space for variables to store loop indices, XOR sums, and the final count.
**Pros:** Simple to understand and implement as it directly follows the problem's definition.; Requires no extra space beyond a few variables for loops and sums.
**Cons:** Highly inefficient due to its cubic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms with stricter time limits for this problem size.
### Explanation
The brute-force method involves a straightforward, exhaustive search. We set up three nested loops to generate every valid triplet of indices `(i, j, k)`. The outermost loop selects the starting index `i`, the second loop selects the split point `j`, and the innermost loop selects the ending index `k`. For each triplet, we must compute two separate XOR sums: `a` for the subarray from `i` to `j-1`, and `b` for the subarray from `j` to `k`. A naive implementation would calculate these sums from scratch each time, leading to an `O(N^5)` complexity. However, we can optimize this by calculating the XOR sums incrementally. For a fixed `i`, as `j` increases, we can update `a`. Similarly, for a fixed `j`, as `k` increases, we can update `b`. This optimization reduces the complexity to `O(N^3)`, which is still computationally expensive but a significant improvement.
### Algorithm
- Initialize a variable `count` to 0.
- Use three nested loops to iterate through all possible triplets `(i, j, k)` satisfying `0 <= i < j <= k < arr.length`.
- The outer loop for `i` runs from `0` to `n-1`.
- The middle loop for `j` runs from `i + 1` to `n-1`.
- The inner loop for `k` runs from `j` to `n-1`.
- Inside the loops, calculate `a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]` and `b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]`.
- To optimize, these XOR sums can be calculated incrementally within their respective loops.
- If `a` is equal to `b`, increment the `count`.
- After all triplets have been checked, return `count`.

## Simplified Condition with Nested Loops
A key mathematical observation simplifies the problem significantly. The condition `a == b`, where `a` and `b` are XOR sums, is equivalent to `a ^ b == 0`. The expression `a ^ b` is the XOR sum of the entire subarray from `i` to `k`. Therefore, the problem is to find the number of triplets `(i, j, k)` where `arr[i] ^ arr[i+1] ^ ... ^ arr[k] == 0`.

For any pair of indices `(i, k)` where the XOR sum of `arr[i...k]` is 0, we can choose any `j` such that `i < j <= k` to form a valid triplet. The number of choices for `j` is `k - i`. This insight allows us to reframe the problem as finding all such `(i, k)` pairs and summing up the `k - i` values.
**Time:** O(N^2), due to the two nested loops required to check all possible subarrays `arr[i...k]`. · **Space:** O(1), as we only use a few variables for the loops, the running XOR sum, and the total count.
**Pros:** Significantly more efficient than the O(N^3) brute-force approach.; The logic is still relatively straightforward and easy to implement.; Maintains O(1) space complexity.
**Cons:** While much better than brute force, the O(N^2) complexity might still be too slow for very large input arrays (though it passes for the given constraints).
### Explanation
This approach leverages the property of the XOR operation. Instead of iterating through `i`, `j`, and `k`, we only need to iterate through `i` and `k`. We use two nested loops: an outer loop for the start index `i` and an inner loop for the end index `k`.

For each `i`, we iterate `k` from `i` to the end of the array. We maintain a running XOR sum for the subarray `arr[i...k]`. If at any point this running XOR sum becomes zero, it means we've found a valid pair `(i, k)`. For this pair, we know there are `k - i` possible values for `j` that will satisfy the original condition. We add this number, `k - i`, to our total count. This process is repeated for all possible start indices `i`.
### Algorithm
- Realize that `a == b` is equivalent to `a ^ b == 0`.
- The expression `a ^ b` is the XOR sum of the entire subarray from `i` to `k`, i.e., `arr[i] ^ ... ^ arr[k]`.
- The problem reduces to finding pairs `(i, k)` where the XOR sum of `arr[i...k]` is 0.
- For each such pair, any `j` with `i < j <= k` forms a valid triplet. The number of such `j`'s is `k - i`.
- Initialize `count = 0`.
- Loop `i` from `0` to `arr.length - 1`.
  - Initialize `current_xor = 0`.
  - Loop `k` from `i` to `arr.length - 1`.
    - Update `current_xor ^= arr[k]`.
    - If `current_xor == 0` and `k > i`, add `k - i` to `count`.
- Return `count`.

## Optimal O(N) Solution using Prefix XOR
This is the most optimal approach, achieving a linear time complexity. It builds upon the simplified condition `XOR(i, k) == 0` and utilizes a prefix XOR array (or a running prefix XOR value) to identify valid `(i, k)` pairs in a single pass. The core idea is that `XOR(i, k) == 0` is equivalent to `prefix_xor[k+1] == prefix_xor[i]`. By storing the counts and indices of previously seen prefix XOR values in hash maps, we can quickly calculate the number of new triplets formed at each step.
**Time:** O(N), where N is the length of the array. We iterate through the array once, and all hash map operations (put, get) take, on average, O(1) time. · **Space:** O(N) in the worst case. If all prefix XOR sums are distinct, the hash maps will store N entries. In the best case (e.g., all elements are 0), the space is O(1).
**Pros:** Most efficient solution with O(N) time complexity.; Solves the problem in a single pass through the array.
**Cons:** The logic is more complex and less intuitive than the previous approaches.; Requires additional space for the hash maps, which can be up to O(N) in the worst case.
### Explanation
We iterate through the array using a single loop with index `k`. We maintain a running `prefixXor` value. The goal is to find, for each `k`, the sum of `k - i` for all `i < k` such that `XOR(i, k) == 0`. This is equivalent to finding `i` where `prefix_xor[i] == prefix_xor[k+1]`.

To do this efficiently, we use two hash maps. `countMap` stores how many times we've seen each prefix XOR value. `indexSumMap` stores the sum of the indices `k` at which each prefix XOR value occurred. 

As we iterate through `k` from `0` to `n-1`, we update `prefixXor`. We then look up this `prefixXor` in our maps. If we've seen this value `c` times before at indices `k_1, k_2, ..., k_c`, we can form `c` new valid ranges ending at the current `k`. The start index `i` for a range found at a previous `k_r` is `k_r + 1`. The number of triplets added is `sum(k - (k_r + 1))`, which simplifies to `c * k - sum(k_r) - c`. We retrieve `c` and `sum(k_r)` from our maps, calculate the contribution, and add it to our total. Finally, we update the maps with the `prefixXor` and the current index `k`.
### Algorithm
- The condition `XOR(i, k) == 0` can be checked efficiently using prefix XORs. Let `p[x] = arr[0] ^ ... ^ arr[x-1]`.
- Then `XOR(i, k) = p[k+1] ^ p[i]`. The condition becomes `p[k+1] == p[i]`.
- We need to calculate `sum(k - i)` over all pairs `(i, k)` where `p[k+1] == p[i]`.
- This can be rewritten as `sum(c * k - sum_of_indices)`, where `c` is the count of previous occurrences of a prefix XOR value and `sum_of_indices` is the sum of their indices.
- Initialize `total_triplets = 0`, `prefix_xor = 0`.
- Use two HashMaps: `countMap` to store frequencies of prefix XORs, and `indexSumMap` to store the sum of indices for each prefix XOR.
- Initialize `countMap` with `{0: 1}` and `indexSumMap` with `{0: -1}` to handle subarrays starting at index 0.
- Loop `k` from `0` to `n-1`:
  - Update `prefix_xor ^= arr[k]`.
  - If `prefix_xor` is in `countMap`, retrieve its count `c` and sum of previous `k`'s `s`.
  - Add `c * k - s - c` to `total_triplets`.
  - Update `countMap` and `indexSumMap` with the current `prefix_xor` and index `k`.
- Return `total_triplets`.

# Solutions
### Java

```java
class Solution {
public
  int countTriplets(int[] arr) {
    int n = arr.length;
    int[] pre = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      pre[i + 1] = pre[i] ^ arr[i];
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int k = j; k < n; ++k) {
          int a = pre[j] ^ pre[i];
          int b = pre[k + 1] ^ pre[j];
          if (a == b) {
            ++ans;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countTriplets(vector<int> &arr) {
    int n = arr.size();
    vector<int> pre(n + 1);
    for (int i = 0; i < n; ++i)
      pre[i + 1] = pre[i] ^ arr[i];
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int k = j; k < n; ++k) {
          int a = pre[j] ^ pre[i], b = pre[k + 1] ^ pre[j];
          if (a == b)
            ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countTriplets(self, arr: List[int]) -> int: n = len(arr) pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] ^ arr[i] ans = 0 for i in range(n - 1): for j in range(i + 1, n): for k in range(j, n): a, b = pre[j] ^ pre[i], pre[k + 1] ^ pre[j] if a == b: ans += 1 return ans

```