Count Triplets That Can Form Two Arrays Of Equal Xor - Leetcode Solution

Problem:

Given an array of n integers, find the number of triplets in the array that can form two arrays of equal XOR. A triplet (i, j, k) is called good if nums[i] ^ nums[i+1] ^ ... ^ nums[j-1] ^ nums[j] == nums[j] ^ nums[j+1] ^ ... ^ nums[k-1] ^ nums[k].

Example 1:

Input: arr = [2,3,1,6,7] Output: 4 Explanation: The triplets are (0,1,2), (0,3,4), (1,2,3), (2,3,4)

Explanation:

The idea is to use prefix xor. Let XOR[i] be the prefix XOR of array arr[0 to i]. We want to partition the array into two parts such that XOR[i]^XOR[j-1] == XOR[j]^XOR[k-1]. This can be simplified to XOR[i]^XOR[j-1]^XOR[k-1] == 0. Therefore, we just need to find all the triplets (i, j-1, k-1) such that XOR[i] == XOR[j-1]^XOR[k-1]. We can use two hash maps to keep track of the frequency of each xor value. The first hash map is used to represent the frequency of XOR values of all subarrays starting from index 0 and the second hash map is used to represent the frequency of XOR values of all subarrays starting from index i for i=0 to n-1. Then, we iterate from i=0 to n and check all possible triplets (i, j-1, k-1) such that XOR[i] == XOR[j-1]^XOR[k-1]. The frequency of XOR[j-1]^XOR[k-1] in the second hash map gives us the count of good triplets.

Detailed Solution:

1. Initialize two hash maps xor1 and xor2, both with default value 0
2. Initialize prefix xor XOR=0
3. For each index i in range 0 to n-1: a. Update XOR as XOR = XOR^arr[i] b. If XOR is present in xor1, then increase its count by 1 c. else add XOR to xor1 with count 1 d. If XOR is present in xor2, then increase its count by 1 e. else add XOR to xor2 with count 1
4. Initialize count=0
5. For each index i in range 0 to n-1: a. Let XOR1 = XOR^arr[i], XOR2 = XOR1^XOR b. If XOR2 is present in xor1, increment count by frequency of XOR2 in xor1
6. Return count.

1