Problem Description

We are given with encoded array, which is XOR of continuous elements of original array i.e encoded[i] = array[i] ^ array[i+1], and we are also given first element of array.. we need to find the original array.

Examples:
Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]

Thought Process

It is one of the easiest problem in bit manipulation concept. We can solve this in less than a minute if we know properties of XOR. If we don't, our brain will be blank and will seem like hard problem.

Let me recap few important properties of XOR :

• a ^ a = 0
• 0 ^ a = a
• (a ^ b) ^ c = a ^ (b ^ c)

Now we know the properties of XOR. Think about how to solve the problem. we have first element. how to find the second element ?

encoded[0] = array[0] ^ array[1]

we know array[0]. what will be output if we XOR first with encoded[0] ?

first ^ encoded[0] => array[0] ^ array[0] ^ array[1] => 0 ^ array[1] => array[1]

we got the second element. Just repeat the same process to get all the remaining elements. That's it.

    def decode(encoded, first)

        result = [first]
        # for every ele, take prev element in original array and do xor
        for ele in encoded :  
            result.append(result[-1] ^ ele)

        return result

     #TC : O(N)
     #SC: O(1)

Conclusion

This problem is kind of prerequisite to solve much bigger problem. We will solve that problem in next article. Until then keep practicing. Leetcode link .

Thanks for reading. Any suggestions, comments, feedback is much appreciated. 👋👋