logicdiscrete

Find an array if array(XOR)array[1:] is given


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]


Solution

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