# Count Triplets That Can Form Two Arrays of Equal XOR

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
```
Example 3:

```Input: arr = [2,3]
Output: 0
```
Example 4:

```Input: arr = [1,3,5,7,9]
Output: 3
```
Example 5:

```Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8
```

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 10^8

Solution:

you have an array : a[0], a[1].... a[n - 1]

First things first:
We need to understand small fact, if xor(a[0....i]) has appeared before at index j then it means xor(a[j+1.....i]) = 0
Another fact, if xor(a[i....j]) = 0 so this subarray will add (j - i - 1) to the answer.

Now say currently we are at index i and let xor([0...i]) = x.

Now say x has occurred 3 times previously at indices (i1, i2, i3)

our answer for i will be = (i - i1 - 1) + (i - i2 - 1) + (i - i3 - 1)

if you simplify this further you get f * i - (i1 + i2 + i3) - f = (i - 1) * f - (i1 + i2 + i3)

f = no. of times x has occurred previously.

(i1 + i2 + i3) = sum of all the indices where x has occurred previously.

```class Solution {
public int countTriplets(int[] arr) {
int[] a = new int[arr.length + 1];
for (int i = 1; i < a.length; i ++) {
a[i] = arr[i - 1];
}
int n = a.length, res = 0, prefix = 0, c, t;
Map<Integer, Integer> count = new HashMap<>(), total = new HashMap<>();
for (int i = 0; i < n; ++i) {
prefix ^= a[i];
c = count.getOrDefault(prefix, 0);
t = total.getOrDefault(prefix, 0);
res += c * (i - 1) - t;
count.put(prefix, c + 1);
total.put(prefix, t + i);
}
return res;
}
}```

Give the observation: For all pairs of i and k, where arr[i] ^ arr[i + 1] ^ ... ^ arr[k] = 0, then any j (i < j <= k) will be good to set as the answer (hint: proof by contradiction, if you cannot understand this trick immediately). So you just need to find all segments where XOR equals zero.

```    public int countTriplets(int[] arr) {
int ans = 0;
int length = arr.length;
for (int i = 0; i < length; i++) {
int xor = arr[i];
for (int j = i + 1; j < length; j++) {
xor ^= arr[j];
if (xor == 0) {
ans += (j - i);
}
}
}
return ans;
}
```

Time complexity: O(N^2)
Space complexity: O(1)