Decode Xored Array - Leetcode Solution

Problem Statement: 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.

Solution: To solve this problem, first, we need to know what is meant by XOR operation. The XOR operator is denoted by ^ and the operation is defined as follows: 1 ^ 1 = 0 0 ^ 1 = 1 1 ^ 0 = 1 0 ^ 0 = 0

Given that encoded[i] = arr[i] XOR arr[i+1], we can say the following: arr[i] XOR encoded[i] = arr[i] XOR arr[i] XOR arr[i+1] = 0 XOR arr[i+1] = arr[i+1] arr[i+1] XOR encoded[i] = arr[i] XOR arr[i+1] XOR arr[i+1] = arr[i]

Using these equations, we can solve the problem by iterating through the encoded array and following these steps:

1. Append the value of first to the answer array.
2. For each encoded value, compute arr[i+1] and append it to the answer array.
3. Update the value of first to be the last value of the answer array.

Once we have iterated through the encoded array, the answer array will contain the original array arr.

Code:

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

1