Problem#
給你一個整數陣列 pref 長度 n，要你回傳一個新的陣列，滿足條件：pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
答案保證唯一。
測資限制#
- $1 \le n \le 10^5$
- $0 \le val \le 10^6$
想法#
XOR 有以下特性：a ^ b = c, c ^ b = a, c ^ a = b
觀察範例後不難得出: b[i] = b[0]^b[1]^...^b[i-1]^a[i]，根據此觀察撰寫程式即可
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$
賞析#
後來看題解才知道原來 b[i] = a[i] ^ a[i-1] 就夠了