Consider we have array a, and second array b = a[1:](just first element of a deleted). We are given array c which is result of XOR, c[i] = a[i]*b[i] (0<=i<len(b)). Can we find array a if we know c ? Also we are given a[0:7]
It's pretty simple to prove that you can't.
c
has one fewer element than a
. If c
represented the same information as a
in a completely recoverable manner, you could compress c
in the same manner, again and again, until you were left with one element. Clearly the transformation is lossy.
Going the other way, there is no unique way to pick a pair of numbers given their XOR. There is a solution no matter what number you pick as the first in the pair.
However, given c
and any element of a
, you can recover a
fully. Given that (x ^ y) ^ y = x ^ (y ^ y) = x
, and c[i] = a[i] ^ a[i + 1]
, it is easy to unwind the values of a
given any a[i]
.
Without loss of generality, let's assume you're given a[0]
. Since c[0] = a[0] ^ a[1]
, we get that a[1] = c[0] ^ a[0]
. Now you can find a[2] = c[1] ^ a[1]
, and so on for all a[i]
.