Decode XORed Array
Problem
An array arr of n non-negative integers was encoded into an array encoded of length n−1, where encoded[i] = arr[i] XOR arr[i+1]. You are also given the first element first = arr[0]. Reconstruct and return the original array arr.
encoded = [1, 2, 3], first = 1[1, 0, 2, 1]def decode(encoded, first):
arr = [first]
for e in encoded:
arr.append(arr[-1] ^ e)
return arrfunction decode(encoded, first) {
const arr = [first];
for (let i = 0; i < encoded.length; i++) {
arr.push(arr[i] ^ encoded[i]);
}
return arr;
}class Solution {
public int[] decode(int[] encoded, int first) {
int[] arr = new int[encoded.length + 1];
arr[0] = first;
for (int i = 0; i < encoded.length; i++) {
arr[i + 1] = arr[i] ^ encoded[i];
}
return arr;
}
}vector<int> decode(vector<int>& encoded, int first) {
vector<int> arr(encoded.size() + 1);
arr[0] = first;
for (int i = 0; i < (int)encoded.size(); i++) {
arr[i + 1] = arr[i] ^ encoded[i];
}
return arr;
}Explanation
Each encoded value is the XOR of two neighbours: encoded[i] = arr[i] ^ arr[i+1]. We already know the very first element, first = arr[0], so the whole array unravels one step at a time.
The key is XOR's self-inverse rule: x ^ x = 0 and x ^ 0 = x. XOR both sides of the definition with arr[i]: arr[i] ^ encoded[i] = arr[i] ^ arr[i] ^ arr[i+1] = arr[i+1]. So given any element we can recover the next one with a single XOR.
Starting from arr[0] = first, we sweep through encoded left to right. At each step the next original value is simply the value we just computed XOR-ed with the current encoded entry: arr[i+1] = arr[i] ^ encoded[i].
Example: encoded = [1, 2, 3], first = 1. Then arr[0] = 1; arr[1] = 1 ^ 1 = 0; arr[2] = 0 ^ 2 = 2; arr[3] = 2 ^ 3 = 1, giving [1, 0, 2, 1]. You can verify by re-encoding: 1^0=1, 0^2=2, 2^1=3.
Every element costs one XOR, so we rebuild the entire array of length n in a single pass.