Find The Original Array of Prefix XOR
Problem
Given pref where pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i], recover arr.
pref = [5, 2, 0, 3, 1][5, 7, 2, 3, 2]def find_array(pref):
arr = [pref[0]]
for i in range(1, len(pref)):
arr.append(pref[i] ^ pref[i - 1])
return arrfunction findArray(pref) {
const arr = [pref[0]];
for (let i = 1; i < pref.length; i++) {
arr.push(pref[i] ^ pref[i - 1]);
}
return arr;
}class Solution {
public int[] findArray(int[] pref) {
int n = pref.length;
int[] arr = new int[n];
arr[0] = pref[0];
for (int i = 1; i < n; i++) {
arr[i] = pref[i] ^ pref[i - 1];
}
return arr;
}
}vector<int> findArray(vector<int>& pref) {
int n = pref.size();
vector<int> arr(n);
arr[0] = pref[0];
for (int i = 1; i < n; i++) {
arr[i] = pref[i] ^ pref[i - 1];
}
return arr;
}Explanation
We are given the running XOR totals pref and must recover the original arr. The escape hatch is XOR's self-cancelling rule: x ^ x = 0, which lets us peel one term off a prefix.
By definition pref[i] = arr[0] ^ ... ^ arr[i] and pref[i-1] = arr[0] ^ ... ^ arr[i-1]. If you XOR these two together, every shared term from arr[0] up to arr[i-1] cancels, leaving just arr[i]. So arr[i] = pref[i] ^ pref[i-1].
The very first element has no previous prefix, so arr[0] is simply pref[0]. Everything after follows the formula above.
Example: pref = [5, 2, 0, 3, 1]. Then arr[0] = 5; arr[1] = 2 ^ 5 = 7; arr[2] = 0 ^ 2 = 2; arr[3] = 3 ^ 0 = 3; arr[4] = 1 ^ 3 = 2, giving [5, 7, 2, 3, 2].
Each element needs just one XOR of two neighboring prefixes, so we recover the whole array in a single pass.