2433. Find The Original Array of Prefix Xor
You are given an integer array pref of size n.
Find and return the array arr of size n that satisfies:
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
Example :
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
第一眼看到覺得很簡單，就是那個xor不知道要怎麼重複算，所以寫個N^2的迴圈
果不其然吃了TLE
之後把xor的結果另外算然後另開一個一樣大小的陣列存起來
大guy4john:
ans[0] = pref[0];
temp[0] = pref[0];
for(i=1;i<prefSize;i++){
ans[i] = temp[i-1] ^ pref[i];
temp[i] = temp[i-1] ^ ans[i];
}
過了是過了但是速度慢空間甚至只贏過個位數
後來從input output關係下去想
pref = [a,b,c,d,e] output = [A,B,C,D,E]
題目說 b = A ^ B 所以 B = A ^ b = a ^ b
c = A ^ B ^ C = a ^ a ^ b ^ C -> C = b ^ c
所以ans[i] 根本就等於 pref[i-1] ^ pref[i]...