前幾天的每日一題，結果光寫題解寫了三天…，這題本來想用動態規劃解，但沒做出來，看題解發現要用互斥或性質來解，在紙上證明了好久才搞懂原理，寫一篇文章記錄一下。

題目描述

給一個整數陣列 arr，其中選出三個索引值 i、j、k，其中 (0 <= i < j <= k < arr.length)。

a 和 b 定義如下：

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

其中 ^ 符號表示互斥或(XOR)操作。

返回使得 a == b 的三元組 (i, j, k) 數目。

範例 1

1
2
3

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)

範例解釋：

  • 當 (i, j, k) = (0, 1, 2) 時，$a = 2,\ b = 3 \oplus 1 = 2$ 符合 a == b 的條件

解題分析

要解這題要先了解 XOR 的規則，下面給出 XOR 的真值表。

a b Output
0 0 0
0 1 1
1 0 1
1 1 0

由真值表可以觀察出 XOR 的規則，兩個輸入不同才為真。

XOR 還有以下性質($\oplus$ 代表互斥或運算符)：

  • $a \oplus a = 0$
  • $a \oplus 0 = a$
  • $a \oplus b = b \oplus a$
  • $a \oplus (b \oplus c) = (a \oplus b) \oplus c$

要求出題目要求區間 i, k 使得 a = b；因為 a = b，根據 $a \oplus a = 0$ 的性質，得出 $a \oplus b=0$，$arr[i]\oplus \cdots \oplus arr[j-1]\oplus arr[j] \oplus \cdots \oplus arr[k] = 0$，也就是說我們只需要從陣列中尋找一串連續的元素，他們的 XOR 結果為 0 即可找到我們要求的區間。

區間裡的元素任意組合互斥或結果都是 0，證明如下（使用性質 $a \oplus (b \oplus c) = (a \oplus b) \oplus c$）：

$$ a = a_1 \oplus a_2 \ b = b_1 \oplus b_2 \ a = b \ a \oplus b = 0 \ (a_1 \oplus a 2) \oplus (b_1 \oplus b_2)=0 \ a_1 \oplus (a_2 \oplus b_1 \oplus b_2) = 0 $$

再來還需要看一個問題，假設陣列 [1, 2, 5, 6]，互斥或結果為 0，那麼可能的組合有以下幾種：

  • $a = 1,\ b = 2 \oplus 5 \oplus 6=1$，(i, j, k) = (0, 1, 3)
  • $a = 1\oplus 2=3,\ b = 5 \oplus 6=3$，(i, j, k) = (0, 2, 3)
  • $a = 1 \oplus 2 \oplus 5=6, \ b=6$，(i, j, k) = (0, 3, 3)

由上可以觀察出當有 n 個連續元素的互斥或結果為 0，則有 $n-1$ 種組合。

因為我們要求連續區間的互斥或結果，可以用陣列儲存連續計算的 XOR 值，這種陣列我們稱為前綴互斥或陣列。 $$ pXor[i] = pXor[i-1] \oplus arr[i] $$ 假設我們有陣列 [1, 2, 3, 4, 7, 9]，pXor[i] 表示前 i 項元素的互斥或結果。

  • 前 0 項互斥或值：$0$
  • 前 1 項互斥或值：$1$
  • 前 2 項互斥或值：$1 \oplus 2=3$
  • 前 3 項互斥或值：$1 \oplus 2 \oplus 3 = 0$
  • 前 4 項互斥或值：$1 \oplus 2 \oplus 3 \oplus 4 = 4$
  • 前 5 項互斥或值：$1 \oplus 2 \oplus 3 \oplus 4 \oplus 7 = 3$
  • 前 6 項互斥或值：$1 \oplus 2 \oplus 3 \oplus 4 \oplus 7 \oplus 9 = 10$

前綴互斥或陣列 pXor = [0, 1, 3, 0, 4, 3, 10]。

假設我們想要求第 3 項到第 6 項的互斥或值，不需要暴力計算 $3 \oplus 4 \oplus 7 \oplus 9=9$，只需要取 $pXor[2]=1 \oplus 2=3$ 和 $pXor[6]=1 \oplus 2 \oplus 3 \oplus 4 \oplus 7 \oplus 9 = 10$，並計算 $pXor[2]\oplus pXor[6]=9$；因為 $3 \oplus 4 \oplus 7 \oplus 9 = (1 \oplus 2) \oplus (1 \oplus 2 \oplus 3 \oplus 4 \oplus 7 \oplus 9)=9$，其中前兩項的 $1 \oplus 2$ 會和前六項的 $1 \oplus 2$ 抵消。

所以我們只需要在互斥或陣列中找尋相同數字的元素 $pXor[i-1] == pXor[k]$，就可以得到區間 $i$ 和 $k$，前面說過當有 $n$ 個元素時，組合數為 $n-1$；那區間 $i \to k$ 則有 $k-i$ 種組合，每次找到 $pXor[i-1] == pXor[k]$ 就把 $k-i$ 加入 ans 變數，最後返回 ans 的值即可。

按照上述邏輯可以寫出以下程式碼。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int countTriplets(vector<int> &arr)
{
    // 前綴互斥或陣列
    vector<int> pXor(arr.size()+1);
    // 前綴互斥或陣列第 0 項為 0，不寫這句也可以，因為 vector 初始化值為 0
    pXor[0] = 0;
    // 計算前綴互斥或陣列
    for(int i = 0; i < arr.size(); i++)
    {
        pXor[i+1] = pXor[i] ^ arr[i];
    }
    int ans = 0;
    // 因為要判斷 pXor[i-1] == pXor[k]，如果 i 從 0 開始會越界
    for(int i = 1; i <= arr.size(); i++)
    {
        for(int k = i+1; k <= arr.size(); k++)
        {
            if (pXor[i-1] == pXor[k])
            {
                ans += k-i;
            }
        }
    }
    return ans;
}
  • 時間複雜度：$O(n^2)$
  • 空間複雜度：$O(n)$

上面我們只在乎 XOR 值出現的 index，那我們可以利用 Hash Table 記錄下來以降低時間複雜度，然後將互斥或值出現的次數也紀錄下來。假設區間 $[i,k]$ 的互斥或值為 0，那之前說過 $j$ 有 $k-i$ 種可能性。假設我們遍歷到 $k$ 時互斥或值為 $x$，而 $x$ 在 $k$ 之前出現過 4 次，分別出現在 $[i_1, i_2, i_3, i_4]$，那 $j$ 有 $(k-i_1)+(k-i_2)+(k-i_3)+(k-i_4)=4 \cdot k - (i_1+i_2+i_3+i_4)$ 種可能；由此我們可以得到下面公式 $count \cdot k - index_sum$。

範例：假設 arr = [1, 1, 1, 1, 1]，pXor = [0, 1, 0, 1, 0, 1]，注意第一個 0 不算在 k 裡面，假設 $k=3$(第三個 0)，在 k 之前出現過 2 次 0，分別位於 0 和 2，那麼有 $(k-0)+(k-2)=2\cdot k - (0+2)=4$ 種可能，並把每一步算出來的組合數加到 ans 中。

重新優化的程式碼如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int countTriplets(vector<int> &arr)
{
    // val 儲存連續互斥或結果
    int ans = 0, val = 0;
    // count 記錄出現次數，total 儲存位置總和
    unordered_map<int, int> count, total;
    for (int k = 0; k < arr.size(); k++)
    {
        val = val ^ arr[k];
        // val 之前沒有出現過
        if (count.find(val) == count.end())
        {
            count[val] = 0;
            total[val] = 0;
        }
        else
        {
            // 前面數學優化的結果：次數*k - 位置總和
            ans += count[val] * k - total[val];
        }
        // val^arr[k] 是用來求前一項的連續互斥或值，這句的作用是把上一項的次數 +1，因為我們計算的時候不會採用當前項的次數
        count[val ^ arr[k]]++;
        // 前一項對應的位置總和 +k，注意我們遍歷的時候 k = 0 時是從 pXor 的第二個元素開始的，所以往前一項加
        total[val ^ arr[k]] += k;
    }
    return ans;
}
  • 時間複雜度：$O(n)$
  • 空間複雜度：$O(n)$

通過率

References