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] <= 108To find the number of triplets, we can utilize prefix XOR which makes checking if two subarrays have equal XOR efficient. For any indices i, j, k in the array, if the XOR from i to j-1 equals the XOR from j to k, we have a valid triplet. Using prefix XOR allows us to calculate this in constant time.
We compute the prefix XOR of the array where prefix[i] is the XOR from the start of the array to index i. For each pair of indices (i, k), if (prefix[i-1] == prefix[k]), then for all j where i <= j <= k, (i, j, k) will form a valid triplet.
In this Python solution, we use a prefix array to store the prefix XOR of the elements. We iterate over all possible pairs (i, k) and check if the XOR from the start to i-1 equals the XOR from the start to k. For every match, we then count the valid j indices that form a triplet.
JavaScript
Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops.
Space Complexity: O(n), due to the storage of the prefix array.
This approach optimizes the first one by reducing redundant checks and efficiently calculating the number of valid triplet indices.
As we calculate the prefix XOR, we maintain a hashmap (or dictionary) which helps in counting valid j values directly, reducing the nested loop complexity by using suffix array observations.
In the Java solution, we use hashmaps to store the frequency and counts of the prefix XORs. This allows us to calculate the number of valid j indices without needing to iterate exhaustively, leveraging hash lookups instead.
C++
Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop.
Space Complexity: O(n), primarily due to hashmap storage.
| Approach | Complexity |
|---|---|
| Approach 1: Utilize Prefix XOR | Time Complexity: O(n^2), where n is the length of the array, as we are using two nested loops. |
| Approach 2: Optimized Prefix XOR Count | Time Complexity: O(n), where n is the array length due to the optimization using hashmaps that distill the double loop. |
Count Triplets That Can Form Two Arrays of Equal XOR - Leetcode 1442 - Python • NeetCodeIO • 10,045 views views
Watch 9 more video solutions →Practice Count Triplets That Can Form Two Arrays of Equal XOR with our built-in code editor and test cases.
Practice on FleetCode