用XOR還原陣列 Find The Original Array of Prefix XOR Leetcode 2433

Alexander Sinn on Unsplash

題目敘述

題目會給我們一個輸入陣列，陣列裡面存放的是每個元素做XOR之後的前綴累積值。

要求我們從累積值還原出原本的陣列元素值。

XOR前綴累積值定義:

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

詳細的題目可在這裡看到

測試範例

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

約束條件

Constraints:

• 1 <= pref.length <= 105
• 0 <= pref[i] <= 106

演算法

其實這題同樣運用到XOR運算子Self inverse的性質

A ⊕ A = 0

依照題目定義

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

我們可以知道

pref[0] = arr[0] 恰好是首項

接著

pref[1] = arr[0] ^ arr[1] 利用Self inverse的性質

計算pref[1] ^ pref[0] = (arr[0] ^ arr[1]) ^ arr[0] = arr[1]

還原出第二項 arr[1]

同理類推

計算pref[2] ^ pref[1] = (arr[0] ^ arr[1] ^ arr[2]) ^ (arr[0] ^ arr[1] )= arr[2]

還原出第三項 arr[2]

可以歸納出一個規律

arr[i] = pref[i] & pref[i-1]

由這個規則，去還原原始陣列元素值即可。

程式碼

class Solution:
　def findArray(self, pref: List[int]) -> List[int]:
　　
　　# Utilize the property of self-inverse
　　# Self-inverse : A ⊕ A = 0
　　# This means that any value XOR’d with itself gives zero.
　　
　　origin = [ pref[0] ]
　　
　　for i in range(1, len(pref)):
　　　
　　　origin.append( pref[i]^pref[i-1] )
　　
　　return origin

複雜度分析

時間複雜度:

O( n ) 迴圈迭代長度為O(n)，和原本的陣列一樣長。

空間複雜度:

O( n ) out-of-place update創造了一個origin array，和原本的陣列長度一樣長。

關鍵知識點

學完這題之後，記得吸收沉澱一下，
回去複習 Single Number 和 Find the difference 這兩題喔，背後用到的都是同樣的觀念，也都用到 XOR 運算子 Self-inverse的成雙成對互相消去的特質。

Reference:

[1] Python/JS/Go/C++ O(n) by XOR self-inverse [w/ Hint] - Find The Original Array of Prefix Xor - LeetCode