Find The Original Array of Prefix Xor — Problem & Solution
Find The Original Array of Prefix Xor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find The Original Array of Prefix Xor is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google, Adobe and Morgan Stanley interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Prefix Sum
- Asked at: Amazon, Google, Adobe, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given pref, where pref[i] is the XOR of arr[0] … arr[i] for some hidden array arr of the same length.
Reconstruct and return arr. The answer is unique.
Example 1
Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: 5 = 5, 5 XOR 7 = 2, 2 XOR 2 = 0, 0 XOR 3 = 3, 3 XOR 2 = 1.
Example 2
Input: pref = [13]
Output: [13]
Example 3
Input: pref = [0,0,0]
Output: [0,0,0]
Constraints
1 <= pref.length <= 1000000 <= pref[i] <= 1000000
Hints for Find The Original Array of Prefix Xor
Hint 1
pref[i] = pref[i-1] XOR arr[i]by definition.Hint 2
XOR is its own inverse, so XOR both sides by
pref[i-1].Hint 3
That gives
arr[i] = pref[i] XOR pref[i-1], witharr[0] = pref[0].
How to solve Find The Original Array of Prefix Xor
The prefix relation inverts directly because XOR undoes itself: knowing consecutive prefixes recovers the element between them.
Approach
- Set
arr[0] = pref[0]. - For each later
i, setarr[i] = pref[i] ^ pref[i-1].
Why it works
From pref[i] = pref[i-1] ^ arr[i], XOR-ing both sides by pref[i-1] gives pref[i] ^ pref[i-1] = arr[i], since x ^ x = 0 and x ^ 0 = x. The reconstruction is therefore forced, which is why the answer is unique.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Using subtraction instead of XOR — the relation is not additive.
- Overwriting
prefin place is fine only if you readpref[i-1]before writingpref[i].
Reference solution
Python
from typing import List
def findArray(pref: List[int]) -> List[int]:
return [pref[0]] + [pref[i] ^ pref[i - 1] for i in range(1, len(pref))]Java
public static int[] findArray(int[] pref) {
int n = pref.length;
int[] out = new int[n];
out[0] = pref[0];
for (int i = 1; i < n; i++) out[i] = pref[i] ^ pref[i - 1];
return out;
}C++
vector<int> findArray(vector<int>& pref) {
int n = (int) pref.size();
vector<int> out(n);
out[0] = pref[0];
for (int i = 1; i < n; i++) out[i] = pref[i] ^ pref[i - 1];
return out;
}JavaScript
var findArray = function(pref) {
var out = [pref[0]];
for (var i = 1; i < pref.length; i++) out.push(pref[i] ^ pref[i - 1]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation