Leetcode 1442. Count Triplets That Can Form Two Arrays of Equal XOR (python)

题目

解法：prefix XOR

这道题目解法基于几个结论：

• We are searching for sub-array of length ≥ 2 and we need to split it to 2 non-empty arrays so that the xor of the first array is equal to the xor of the second array. This is equivalent to searching for sub-array with xor = 0. Because XOR for two same number is 0.
• if xor for an array is 0, then pick any position to split the arry to two subarrays, the xor for the subarrays should be the same
• prefix xor helps to reduce the time complexity to O(n^2)

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        if n<2:
            return 0
        prefix_xor = [0]
        tmp = 0
        for num in arr:
            tmp ^= num
            prefix_xor.append(tmp)
        
        #print(prefix_xor)
        
        ans = 0
        for i in range(n+1):
            for j in range(i+2,n+1):
                if prefix_xor[j]^prefix_xor[i] == 0:
                    #print(j,i)
                    ans += j-i-1
        
        return ans