Watch 10 video solutions for Count Triplets That Can Form Two Arrays of Equal XOR, a medium level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 10,848 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
Constraints:
1 <= arr.length <= 3001 <= arr[i] <= 108Problem Overview: Given an integer array arr, count triplets (i, j, k) where 0 ≤ i < j ≤ k < n and the XOR of arr[i..j-1] equals the XOR of arr[j..k]. The task reduces to identifying segments where two adjacent subarrays share the same XOR value.
Approach 1: Utilize Prefix XOR (O(n2) time, O(n) space)
Compute a prefix XOR array where px[i] stores the XOR of elements from index 0 to i-1. Using the XOR identity a ^ a = 0, the condition arr[i..j-1] == arr[j..k] becomes px[i] == px[k+1]. Iterate over all pairs (i, k) and when the prefix XOR values match, every index between them can serve as a valid split point j. Each match contributes k - i triplets. This approach directly leverages properties of prefix sum-style preprocessing with XOR operations and is easy to implement but requires a quadratic scan.
Approach 2: Optimized Prefix XOR Count (O(n) time, O(n) space)
Track how often each prefix XOR value appears while scanning the array once. Maintain two hash maps: one for frequency of each prefix XOR and another for the total index sum where that XOR occurred. When the current prefix XOR repeats, it means earlier positions can form valid segments with the current index. The number of new triplets depends on how many times that XOR appeared and the distance between indices. Each step performs constant-time hash lookups, turning the quadratic search into a linear pass. This technique combines hash table counting with XOR prefix properties from bit manipulation.
Recommended for interviews: The optimized prefix XOR counting approach is what most interviewers expect. The quadratic prefix XOR version shows that you understand the mathematical reduction px[i] == px[k+1]. The linear hash‑map solution demonstrates deeper algorithmic insight and reduces the complexity to O(n), which is the optimal bound for scanning the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix XOR Pair Enumeration | O(n^2) | O(n) | Useful for understanding the XOR property and during initial reasoning in interviews |
| Optimized Prefix XOR with Hash Counting | O(n) | O(n) | Best general solution; handles large arrays efficiently with constant‑time hash lookups |