- Published on

# Decode XORed Array.

**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