Pankaj Tanwar
Published on

Decode XORed Array.

––– views

Problem of the day - Decode XORed Array

Tag - Easy.

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Input: encoded = [1,2,3], first = 1
> Output: [1,0,2,1]
> Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

At first glance, problem seems a bit tricky but it's not. So, I have the first element, I just need to do reverse of XOR to find the next value and continue doing so till the last element.

Well, what's the reverse of XOR?

To my surprise, the reverse of XOR is also XOR.

if a = b^c than b = a^c and c = a^b.

That was the bit-manipulation trick for this problem.

Here is the code -

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> res{first};
        for(auto val: encoded) res.push_back(first ^= val);
        return res;
    }
};

P.S. - I really like the way this code is shortened.

You might like previous editions of my coding diary

Tweet this article