Count Triplets That Can Form Two Arrays of Equal XOR

medium bitwise prefix xor

Problem

Given an integer array arr, pick three indices with 0 ≤ i < j ≤ k < n. They cut out two adjacent pieces: a is the XOR of arr[i..j-1] and b is the XOR of arr[j..k]. Count how many triplets (i, j, k) make a == b.

The array has up to 300 elements, each between 1 and 10⁸.

Inputarr = [2,3,1,6,7]

Output4

Prefix XORs are [0,2,1,0,6,1]: prefix[0]=prefix[3] gives (0,1,2) and (0,2,2); prefix[2]=prefix[5] gives (2,3,4) and (2,4,4).

arr (comma-separated integers)

def count_triplets(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for t in range(n):
        prefix[t + 1] = prefix[t] ^ arr[t]
    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

function countTriplets(arr) {
  const n = arr.length;
  const prefix = new Array(n + 1).fill(0);
  for (let t = 0; t < n; t++) {
    prefix[t + 1] = prefix[t] ^ arr[t];
  }
  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;
}

int countTriplets(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n + 1];
    for (int t = 0; t < n; t++) {
        prefix[t + 1] = prefix[t] ^ arr[t];
    }
    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;
}

int countTriplets(vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);
    for (int t = 0; t < n; t++) {
        prefix[t + 1] = prefix[t] ^ arr[t];
    }
    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;
}

Explanation

The two halves satisfy a == b exactly when a ^ b == 0, and a ^ b is just the XOR of the whole range arr[i..k]. So the split point j drops out of the condition entirely: we only need ranges whose total XOR is zero.

Range XORs are read off a prefix XOR array: prefix[0] = 0 and prefix[t+1] = prefix[t] ^ arr[t]. Then the XOR of arr[i..k] equals prefix[i] ^ prefix[k+1], which is zero exactly when prefix[i] == prefix[k+1].

For each such pair (i, k), every split point j with i < j ≤ k produces a valid triplet, because the condition never mentioned j. That is k - i triplets per matching pair, so we scan all pairs and add k - i whenever the prefixes agree.

Default example arr = [2,3,1,6,7]: the prefixes are [0, 2, 1, 0, 6, 1]. The value 0 repeats at positions 0 and 3, giving i = 0, k = 2 and contributing 2; the value 1 repeats at positions 2 and 5, giving i = 2, k = 4 and contributing another 2; the answer is 4.

Building the prefix array is O(n) and the pair scan checks O(n²) pairs, each in constant time, so the total is O(n²) with O(n) extra space — comfortably fast for n ≤ 300. (A hash map keyed by prefix value, tracking counts and index sums, can even bring this down to O(n).)

Time: O(n²) Space: O(n)