LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                for (int k = j; k < n; ++k)
                    if (dp[i] == dp[k + 1])
                        ++ans;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int k = i + 1; k < n; ++k)
                if (dp[i] == dp[k + 1])
                    ans += k - i;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        unordered_map<int, int> freq, sum;
        for (int i = 0; i < n; ++i) {
            if (freq.find(dp[i + 1]) != freq.end())
                ans += freq[dp[i + 1]] * i - sum[dp[i + 1]];
            ++freq[dp[i]];
            sum[dp[i]] += i;
        }
        return ans;
    }
};