1260. Recovering the Array From Its Running XOR
A log recorded only the RUNNING XOR of a stream of readings. Position i of
the log holds a[0] ^ a[1] ^ ... ^ a[i]. Print the original readings.
log 1 3 0 4 1 0
a 1 2 3 4 5 1
because 1 = 1, 1 ^ 2 = 3, 3 ^ 3 = 0, 0 ^ 4 = 4, 4 ^ 5 = 1,
1 ^ 1 = 0`.
## What most people try first
Rebuild each reading by XORing out everything before it: to recover a[i],
take log[i] and XOR it against all the readings already recovered. That is
correct and it is O(n^2), which at n = 200000 is 4 * 10^10 operations for
something a single XOR per position does.
Noticing why it is wasteful is the whole point: everything already recovered
XORs together to exactly log[i-1], which the input handed you for free.
## XOR is its own inverse
Problem 731 uses the forward direction, XOR(a[l..r]) = P[r+1] ^ P[l]. This is
the same identity used backwards, at the narrowest possible range:
a[i] = log[i] ^ log[i - 1] for i >= 1
a[0] = log[0]
It is exact rather than approximate because v ^ v = 0 for every v and
v ^ 0 = v. So log[i] ^ log[i-1] is
(a[0]^...^a[i]) ^ (a[0]^...^a[i-1]), and every term except a[i] appears
twice and cancels. No subtraction, no borrow, no separate inverse operation:
the only reason a prefix SUM needs subtraction is that addition has one, and
XOR does not need one at all.
The i = 0 case is not an exception if you imagine log[-1] = 0, since
log[0] ^ 0 = log[0]. Writing the loop that way removes the special case
entirely, which is the shape worth learning.
## Why the recovered array is unique
Given the log, the array is forced: a[0] must be log[0], and then each
a[i] is forced in turn. So there is exactly one answer, and any implementation
that produces a different one is wrong rather than differently right.
## Width
Readings are at most 1073741823, which is 2^30 - 1, so every value and every
running XOR stays below 2^30 and never reaches bit 31. The whole computation
therefore fits in a signed 32-bit integer, whose limit is 2147483647, and
JavaScript's ^ is safe here with plain Numbers: its coercion to signed 32
bits cannot change a value that already fits. This is the only width in this
block where that is true without qualification, and it is stated rather than
assumed because #1261 immediately next door is not like this.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each logged value ≤ 1073741823`
Input
The first line contains the integer n.
The second line contains n integers: the running XOR at each position.
Output
Print the n original readings on one line, in order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.