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]...