Decode XORed Array (LeetCode 1720): One XOR Property Does All the Work

LeetCode 1720 gives you an array encoded where encoded[i] = arr[i] XOR arr[i+1], plus the first element first. You have to rebuild the original arr. It is an "easy" problem, but interviewers like it because it checks whether you actually understand XOR instead of memorizing tricks.

The one fact you need

XOR is its own inverse: x ^ x = 0 and x ^ 0 = x. So if e = a ^ b, then e ^ a = a ^ b ^ a = b. Knowing one neighbor and the encoded value always gives you the other neighbor.

Solution

def decode(encoded, first):
    arr = [first]
    for e in encoded:
        arr.append(arr[-1] ^ e)
    return arr

Time is O(n) and the output array is the only extra space. Walk through encoded = [1,2,3], first = 1: 1, then 1^1 = 0, then 0^2 = 2, then 2^3 = 1, giving [1,0,2,1].

How to talk about it in the interview

If you want to rehearse explaining bit tricks like this under time pressure, AI interview assistant tools can give you live feedback during practice rounds. Disclosure: I work on Linkjob AI.