Sponsored
Sponsored
To 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.
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.
1def countTriplets(arr):
2 n = len(arr)
3 prefix = [0] * (n + 1)
4 for i in range(n):
5 prefix[i + 1] = prefix[i] ^ arr[i]
6 count = 0
7 for i in range(n):
8 for k in range(i + 1, n):
9 if prefix[i] == prefix[k + 1]:
10 count += k - i
11 return countIn 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.
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.
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.
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5int countTriplets(vector<int>& arr) {
int n = arr.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] ^ arr[i];
}
int count = 0;
unordered_map<int, int> map, cnt;
for (int k = 0; k < n; k++) {
if (map.find(prefix[k + 1]) != map.end()) {
count += map[prefix[k + 1]] * k - cnt[prefix[k + 1]];
}
map[prefix[k]]++;
cnt[prefix[k]] += k;
}
return count;
}This C++ solution adapts the Java approach using unordered_maps for optimized key lookups. It efficiently calculates valid triplets by managing prefix XOR occurrences and indices without needless iteration.