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

https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

O(N^3) Use prefix brutal force check all (i,j,k) triplets

I come up with it during contest but it's not fast enough

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cnt = 0
        n = len(arr)
        if n == 0:
            return 0
        xor = [0,arr[0]]
        for num in arr[1:]:
            xor.append(xor[-1] ^ num)
        
        for i in range(n-1):
            for j in range(i+1,n):
                for k in range(j,n):
                    if xor[i] ^ xor[j] == xor[j] ^ xor[k+1]:
                        #print("{} {} {}".format(i,j,k))
                        cnt+=1
        return cnt

This one is more efficient since we only need to check pair (i,k) here where prefix[i-1] == prefix[k]

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cnt = 0
        n = len(arr)
        if n == 0:
            return 0
        xor = [0,arr[0]]
        for num in arr[1:]:
            xor.append(xor[-1] ^ num)
        
        for i in range(1,n):
            for k in range(i+1,n+1):
                if xor[i-1] == xor[k]:
                    #print("{} {} {}".format(i,j,k))
                    cnt+= k-i
        return cnt

now There is O(N) Solution use hashmap and prefix

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cnt = 0
        n = len(arr)
        curr = 0
        d = {
            0: [1,0] #1 is freq and 0 is sum of previous index whose prefix[i] == 0
        }
        if n == 0:
            return 0
        for i, num in enumerate(arr,1):
            curr = curr ^ num
            #print(curr)
            if curr in d:
                freq, preSum = d[curr]
                #print("freq, preSum : {} {}".format(freq,preSum))
                d[curr] = [freq+1, preSum +i]
                cnt += freq * (i-1) - preSum
            else:
                d[curr] = [1,i]
        return cnt