Given an array of integers arr.

We want to select three indices i, j and k where (0 &lt;= i &lt; j &lt;= k &lt; 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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 300
	1 &lt;= arr[i] &lt;= 108


class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        s = [0]
        n = len(arr)
        if n <= 1:
            return 0 
        for i in range(n):
            s.append(s[-1]^arr[i])
        # a = s[i] ^ s[j], b = s[j] ^ s[k+1]  
        count = defaultdict(int)
        # a = b <-> a ^ b == 0 <-> (s[i] ^ s[j]) ^ (s[j] ^ s[k+1]) == 0 
        # <-> s[i] ^ (s[j] ^ m ) = 0 (where m = s[j] ^ s[k+1])
        # <-> s[i] ^ s[k+1] == 0 <-> s[i] == s[k+1]
      
        res = 0 
        # len(s) == n+1, 0<=i<=n-2, 1<=k<=n-1, i+1<=j<=k
        for i in range(n-1):
            for k in range(i+1, n):
                if s[i] == s[k+1]:
                    res += (k-i)
        return res 
class Solution {
    public int countTriplets(int[] arr) {
        int count=0;

        for(int i=0;i<arr.length;i++){
            int val=0;
            val=val^arr[i];
            for(int k=i+1;k<arr.length;k++){
                val=val ^ arr[k];
                if(val==0) count+=k-i;
            }
        }
        return count;
    }
}
class TrieNode {
public:
    int numOfIndex;
    int sumOfIndex;
    TrieNode* child[2];
    
    TrieNode() : numOfIndex(0), sumOfIndex(0) {
        child[0] = NULL;
        child[1] = NULL;
    }
};
class Solution {
public:
    void addNumber(TrieNode* root, int num, int idx){
        for( int i = 31; i >= 0; i--){
       
            int bit = 1 & (num >> i) ;
        
            if ( root->child[bit] == NULL){
                root->child[bit] = new TrieNode();
            }
            root = root->child[bit];
        }
        root->sumOfIndex += idx;
        root->numOfIndex++;
    }
    int calculateIndexPair(TrieNode* root, int num, int idx){
        for( int i = 31; i >= 0; i--){
            int bit = 1 & (num >> i);
        
            if (root->child[bit] == NULL){
                return 0;
            }
            root = root->child[bit];
        }
        return (((root->numOfIndex) * idx) - (root->sumOfIndex));
    }
    int countTriplets(vector<int>& arr) {
        long long ans=0;
        int XOR = 0;
        TrieNode* root = new TrieNode();
    
        for ( int i = 0 ; i < arr.size(); i++){
            addNumber(root, XOR, i);
            XOR ^= arr[i];
            ans = (ans + calculateIndexPair(root, XOR, i)) % 1000000007;
        }
        return ans;
    }
};
/**
 * @param {number[]} arr
 * @return {number}
 */
var countTriplets = function(arr) {
    let count = 0
    for(let i=0;i<arr.length;i++){
        let xor = arr[i]
        for(let j=i+1;j<arr.length;j++){
            xor ^= arr[j]
            if(xor == 0){
                count += (j-i)
            }
        }
    }
    return count
};
Count Triplets That Can Form Two Arrays of Equal XOR