Problem Statement 📃

After reading the question, if you wonder about solving the problem already in the earlier post, then you are actually correct. This is the extension of previous question. For starters, who wish to revise the XOR properties or to remember how we solve previous problem, please gloss over previous article.

The only difference in this and the previous question is here we are not given the value of first element. By doing so, this problem essentially became medium level.

The leetcode link for this question can be accessed from here

In brief,

• Original array is permutation of first N positive integers
• Length of original array = length of encoded + 1
• encoded[i] = original[i] xor original[i+1]

Examples:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

All we need is to find the first element of the permutation and from there its just previous problem.

Deep Dive of the problem

First, lets work on what we have based on the question let say size of encoded is 4 => length of permutation array is 5. consider permutation = [a, b, c, d, e] as our original array.

perm = [a, b, c, d, e]
then encoded = [a^b, b^c, c^d, d^e]

we can have xor of all elements of perm array i.e all_xor = a^b^c^d^e

Using this we need to find the first element that is a.

Lets extract all the pairs that can be found with a :

- a^b   => encoded[0]
- (a^b)  xor encoded[1]   => (a^b) xor (b^c)  => a^c
- (a ^ c) xor encoded[2]  => (a ^ c) xor (c ^ d)  => a ^ d
- (a ^ d) xor encoded[3]  => (a ^ d) xor (d ^ e) => a ^ e

We have 4 pairs with element a, and all xor which is formed by all the elements.

Uff, all the hordwork is done. All that left is now to take xor of all above pairs and also include all xor (which we calculated earlier)

(a ^ b) xor (a ^ c) xor (a ^ d) xor (a ^ e) xor (a ^ b ^ c ^ d ^ e)  

=> a  ( out of 5a's, 4 will cancel each other and all elements repeated 
twice will cancel each other ~ remember XOR property. a ^a  = 0)

Once we got the value of a, we just do XOR with values in encoded array. As it is already explained in the previous article, Not wasting your time. Its time to dive into the code !!!

def decode(encoded) :

    # we know perm is first N numbers
    N = len(encoded) + 1
    all_xor = 0
    for i in range(N+1) :
        all_xor = all_xor ^ i

    # find the pairs with first elements

    first_pair = encoded[0]
    # we dont need to maintain extra space... single variable suffice
    result = [first_pair]    

    for ele in encoded[1:] :
        pair = result[-1] ^ ele
        result.append(pair)

    # now take XOR with all pairs with all_xor

    for ele in result :
        all_xor = all_xor ^ ele

    # now all_xor contains first element

    result = [all_xor] 
    for ele in encoded :
        result.append(result[-1] ^ ele)

    return result   

    #TC: O(N)
    #SC: O(1)   as we don't count result array

Conclusion

This problem is little tricky and need deep understanding of xor and how to generate pairs that are forming with first element. So if anything is not clear, or any questions please feel free to comment and I will be happy to answer. As always any suggestions, feedback is always welcome.

Thanks for reading. 👋👋