Leet Code Daily 2024-05-30 - Count Triplets That Can Form Two Arrays of Equal XOR

Description

Solution

Preffix Sum + Hash

First, let's define preffix sum under XOR operator:

S_{i} = \begin{cases} 0 & i = 0 \\ S_{i - 1} \oplus A_{i - 1} & 1 \leq i \leq n \\ \end{cases}

Then we know, for any valid triplet (i, j, k):

\begin{align} S_{j} \oplus S_{i} &= S_{k + 1} \oplus S_{j} \\ S_{i} &= S_{k + 1} \\ \end{align}

We know $0 <= i < j <= k < n$ ; so for any $i, k$ where $S_{i} = S_{k + 1}$ , there are $k - i$ possible $j$ values.

Then we can hash $S_{i}$ to count them in $O(n)$ time.

Code

c++

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        vector<int> s = {0};
        for (const auto& a : arr) {
            s.push_back(s.back() ^ a);
        }
        int ans = 0;
        unordered_map<int, int> cnt, sum;
        for (int i = 0; i < arr.size(); i++) {
            ans += cnt[s[i + 1]] * i - sum[s[i + 1]];
            cnt[s[i]]++;
            sum[s[i]] += i;
        }
        return ans;
    }
};

Leet Code Daily 2024-05-30 - Count Triplets That Can Form Two Arrays of Equal XOR

Solution

Code

COMMAND INTERFACE

:help aguang.xyz