Code Implementation

class Solution:
    def countTriplets(self, arr):
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ arr[i]
        count = 0
        for i in range(n):
            for k in range(i + 1, n):
                if prefix[i] == prefix[k + 1]:
                    count += k - i
        return count
      

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = i + 1; k < n; ++k) {
                if (prefix[i] == prefix[k + 1]) {
                    count += k - i;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = i + 1; k < n; ++k) {
                if (prefix[i] == prefix[k + 1]) {
                    count += k - i;
                }
            }
        }
        return count;
    }
}
      

var countTriplets = function(arr) {
    const n = arr.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] ^ arr[i];
    }
    let count = 0;
    for (let i = 0; i < n; ++i) {
        for (let k = i + 1; k < n; ++k) {
            if (prefix[i] === prefix[k + 1]) {
                count += k - i;
            }
        }
    }
    return count;
};
      

Problem Description

Given an array of integers arr, you are to count the number of triplets (i, j, k) where 0 <= i < j <= k < arr.length such that the XOR of the subarray arr[i] ^ arr[i+1] ^ ... ^ arr[j-1] is equal to the XOR of the subarray arr[j] ^ arr[j+1] ^ ... ^ arr[k].

• You must count all such triplets in the array.
• Elements can be reused in different triplets, but each triplet must have unique indices.
• Constraints:
  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

The goal is to return the total number of valid triplets that meet the above XOR condition.

Thought Process

The problem asks us to find all triplets (i, j, k) such that two subarrays have equal XOR. At first, it might seem that we need to check every possible triplet, which would require three nested loops. However, this would be inefficient for larger arrays.

To optimize, let's analyze the XOR property: if a == b, then a ^ b == 0. So, for our subarrays:
If arr[i] ^ arr[i+1] ^ ... ^ arr[j-1] == arr[j] ^ arr[j+1] ^ ... ^ arr[k], then the XOR of the entire subarray from i to k is zero.

This insight allows us to reduce the problem to finding all pairs (i, k) where the XOR from i to k is zero. For each such pair, there are k - i possible values for j (since i < j <= k).

This reduces the complexity from three nested loops to two, making the solution efficient enough for the problem's constraints.

Solution Approach

Let's break down the optimized solution step by step:

1. Compute Prefix XOR:
   • Create a prefix XOR array, where prefix[i] stores the XOR of all elements from the start up to index i-1 (exclusive).
   • This allows us to compute the XOR of any subarray arr[i]...arr[k] as prefix[k+1] ^ prefix[i].
2. Find Valid (i, k) Pairs:
   • Iterate over all pairs (i, k) with i < k.
   • If prefix[i] == prefix[k+1], then the XOR from i to k is zero.
3. Count Triplets:
   • For each valid (i, k), every j with i < j <= k forms a valid triplet.
   • There are exactly k - i such j values.
   • Add k - i to the answer for each valid pair.
4. Return the Total Count:
   • Sum up all valid triplets and return the result.

This approach leverages the properties of XOR and prefix sums for efficient computation, avoiding unnecessary nested loops.

Example Walkthrough

Let's walk through an example with arr = [2, 3, 1, 6, 7].

1. Compute Prefix XOR:
   • prefix[0] = 0
   • prefix[1] = 0 ^ 2 = 2
   • prefix[2] = 2 ^ 3 = 1
   • prefix[3] = 1 ^ 1 = 0
   • prefix[4] = 0 ^ 6 = 6
   • prefix[5] = 6 ^ 7 = 1
   • So, prefix = [0, 2, 1, 0, 6, 1]
2. Find Valid (i, k) Pairs:
   • Check all pairs (i, k) where i < k and prefix[i] == prefix[k+1]
   • For example, (i=0, k=2): prefix[0]=0, prefix[3]=0 → valid, so add (2-0)=2 triplets: (0,1,2), (0,2,2)
   • Continue for all pairs, accumulating the count.
3. Count Triplets:
   • For each valid pair, add k-i to the result.
4. Final Result:
   • The total count after all iterations is 4 (for this specific example).

This process ensures all valid triplets are counted efficiently.

Time and Space Complexity

• Brute-force approach:
  • Three nested loops over i, j, k → O(n³) time.
  • Not feasible for n up to 300.
• Optimized approach:
  • Compute prefix XOR in O(n) time and space.
  • Two nested loops over i and k (with i < k) → O(n²) time.
  • Space complexity is O(n) for the prefix array.

The optimized solution is efficient and suitable for the problem's constraints.

Summary

In this problem, we leveraged the properties of XOR and prefix sums to efficiently count all triplets where two subarrays have equal XOR. The key insight was recognizing that the XOR of the full subarray being zero is equivalent to the required condition, allowing us to reduce the problem to O(n²) time using prefix XOR. This approach avoids unnecessary computation and demonstrates the power of mathematical properties in algorithm optimization.