# 1442. Count Triplets That Can Form Two Arrays of Equal XOR

## Description

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

## Solutions

• 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;
}
}

• 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;
}
};

• 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


• func countTriplets(arr []int) int {
n := len(arr)
pre := make([]int, n+1)
for i := 0; i < n; i++ {
pre[i+1] = pre[i] ^ arr[i]
}
ans := 0
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
for k := j; k < n; k++ {
a, b := pre[j]^pre[i], pre[k+1]^pre[j]
if a == b {
ans++
}
}
}
}
return ans
}