1720. Decode XORed Array

Decode XORed Array

題目描述：已知一個長度為 n 的整數陣列 arr（原始），現在有一個長度為 n-1 的 encoded 陣列，其中 encoded[i] = arr[i] XOR arr[i+1]。另外給定 arr[0] = first（第一個元素的值）。請解碼並回傳原始陣列 arr。

解題思路：利用 XOR 的關鍵性質：a XOR b = c 則 a XOR c = b（自反性）。

已知 encoded[i] = arr[i] XOR arr[i+1]，兩邊同時與 arr[i] 做 XOR：

arr[i] XOR encoded[i] = arr[i] XOR arr[i] XOR arr[i+1] = 0 XOR arr[i+1] = arr[i+1]

因此 arr[i+1] = arr[i] XOR encoded[i]。從已知的 arr[0] = first 出發，逐步計算 arr[1], arr[2], ...，線性掃描一遍即可還原完整陣列。

時間複雜度：O(n)——只需一次線性掃描 encoded 陣列（長度 n-1），每步做一次 XOR 運算（O(1)），整體為 O(n)。

空間複雜度：O(n)——輸出陣列 arr 長度為 n；若不計輸出空間，額外空間為 O(1)（只用到幾個整數變數）。

方法一：前綴 XOR 計算 定義前綴 XOR prefix[k] = arr[0] XOR arr[1] XOR ... XOR arr[k]。由 encoded[i] = arr[i] XOR arr[i+1]，可推出 encoded[0] XOR encoded[1] XOR ... XOR encoded[i-1] = arr[0] XOR arr[i]，故 arr[i] = first XOR (encoded[0] XOR ... XOR encoded[i-1])。可先建構 encoded 的前綴 XOR 陣列，再一次計算所有 arr[i]，時間空間同為 O(n)，但需兩次掃描，略遜於直接遞推。

方法二：原地計算（In-place，若允許修改 encoded） 若允許修改 encoded，可擴展其長度為 n，在 encoded 陣列前插入 first，然後原地利用 encoded[i] ^= encoded[i-1] 轉換為前綴 XOR，即為答案。節省額外空間但修改了輸入，一般面試中不推薦。

方法三：反向解碼 若另外給定 arr[n-1]（最後一個元素）而非 arr[0]，可從後往前解碼：arr[i] = arr[i+1] XOR encoded[i]。此變體展示 XOR 解碼的對稱性，可用於驗證：正向解碼的結果若從後往前再解一次應回到原始 first。

1. 若 encoded[i] = arr[i] + arr[i+1]（加法而非 XOR），給定 arr[0]，能否同樣逐步還原？此時數值溢位問題如何處理？
2. XOR 的自反性（a XOR a = 0）在密碼學的「一次性密碼本（One-Time Pad）」中如何應用？本題的解碼過程與 OTP 的解密有何相似之處？
3. 若 encoded 陣列本身也被加密（例如每個元素再 XOR 一個固定的密鑰 k），在不知道 k 的情況下，能否還原 arr？需要哪些額外條件？