Find The Original Array of Prefix Xor
MedPrompt
You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
Note that ^ denotes the bitwise-xor operation.
It can be proven that the answer is unique.
Example 1:
Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.Example 2:
Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.
Constraints:
1 <= pref.length <= 1050 <= pref[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This naive approach directly implements the definition of the prefix XOR array. To find each element arr[i], it re-computes the XOR sum of all previously found elements arr[0] through arr[i-1]. While correct, this method is computationally expensive.
Algorithm
- Create a new integer array
arrof the same size aspref. - If
prefis not empty, setarr[0] = pref[0]. - Iterate with a loop from
i = 1topref.length - 1. - Inside the loop, calculate the prefix XOR of the already computed part of
arr:prefixXorOfArr = arr[0] ^ arr[1] ^ ... ^ arr[i-1]. This requires a nested loop. - Calculate
arr[i] = prefixXorOfArr ^ pref[i]. - After the loop, return
arr.
Walkthrough
The fundamental relationship is pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]. From this, we can derive arr[i] = (arr[0] ^ arr[1] ^ ... ^ arr[i-1]) ^ pref[i]. The algorithm proceeds by building the arr array element by element. For each arr[i], it first iterates through arr[0] to arr[i-1] to calculate their XOR sum, and then XORs this sum with pref[i] to find arr[i]. This repetitive calculation of the prefix XOR for arr makes the approach inefficient.
class Solution { public int[] findArray(int[] pref) { int n = pref.length; if (n == 0) { return new int[0]; } int[] arr = new int[n]; arr[0] = pref[0]; for (int i = 1; i < n; i++) { // Re-compute prefix XOR of arr int prefixXorOfArr = 0; for (int j = 0; j < i; j++) { prefixXorOfArr ^= arr[j]; } arr[i] = prefixXorOfArr ^ pref[i]; } return arr; }}Complexity
Time
O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times to re-compute the prefix XOR. This leads to a quadratic runtime.
Space
O(n) - A new array of size `n` is created to store the result.
Trade-offs
Pros
It's a straightforward implementation of the mathematical definition, making it easy to conceptualize.
Cons
Highly inefficient due to the nested loops, resulting in quadratic time complexity.
Will likely cause a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
This optimized approach uses the properties of XOR to derive a direct relationship between adjacent elements of the pref array and the elements of the arr array. This avoids the costly re-computation of the brute-force method and solves the problem in a single pass.
Algorithm
- Create a result array
arrof sizen. - Handle the base case:
arr[0] = pref[0]. - Iterate from
i = 1ton-1. - For each
i, apply the formula:arr[i] = pref[i-1] ^ pref[i]. - Return
arr.
Walkthrough
We can observe the following relationships:
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1] ^ arr[i]pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]
By noticing that pref[i] is just pref[i-1] XORed with arr[i], we get pref[i] = pref[i-1] ^ arr[i]. Using the XOR property that if a = b ^ c, then c = a ^ b, we can find arr[i] with a simple formula: arr[i] = pref[i-1] ^ pref[i] for i > 0. The base case remains arr[0] = pref[0]. This allows us to compute each element of arr in constant time.
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 - 1] ^ pref[i]; } return arr; }}Complexity
Time
O(n) - We iterate through the array once, performing a constant number of operations at each step.
Space
O(n) - A new array of size `n` is allocated for the output.
Trade-offs
Pros
Optimal time complexity of O(n).
The logic is clean and easy to implement once the XOR property is understood.
Cons
Uses O(n) extra space for the result array, which can be optimized further if in-place modification is allowed.
This is the most efficient approach, optimizing the single-pass solution to use constant extra space. It achieves this by modifying the input array pref directly to store the resulting arr values, cleverly avoiding the need for a separate result array.
Algorithm
- Iterate from the end of the array to the second element, i.e., from
i = n-1down to1. - In each iteration, update the current element with the result of the XOR operation:
pref[i] = pref[i-1] ^ pref[i]. - The first element
pref[0]is already correct, asarr[0] = pref[0], so it's left untouched. - Return the modified
prefarray.
Walkthrough
This approach uses the same formula as the previous one: arr[i] = pref[i-1] ^ pref[i]. The goal is to store the result arr in the pref array itself to save space. A naive forward in-place update (pref[i] = pref[i-1] ^ pref[i]) would fail because when we calculate the next element arr[i+1], we need the original pref[i], which we would have already overwritten. The solution is to iterate backward. When we calculate arr[i] (and store it in pref[i]), we use pref[i-1], which has not yet been modified. This ensures the calculation for each element is correct.
class Solution { public int[] findArray(int[] pref) { for (int i = pref.length - 1; i > 0; i--) { pref[i] = pref[i] ^ pref[i - 1]; } return pref; }}Complexity
Time
O(n) - We still perform a single pass over the array.
Space
O(1) - No new array is allocated; the modification happens in-place. The space for the returned array is the input array itself.
Trade-offs
Pros
Optimal time O(n) and space O(1) complexity.
Very memory efficient, which is ideal for very large inputs or memory-constrained environments.
Cons
Modifies the input array, which can be an unwanted side effect if the original data is needed elsewhere.
The backward iteration might be slightly less intuitive at first glance compared to a forward pass.
Solutions
Solution
class Solution { public int [] findArray ( int [] pref ) { int n = pref . length ; int [] ans = new int [ n ]; ans [ 0 ] = pref [ 0 ]; for ( int i = 1 ; i < n ; ++ i ) { ans [ i ] = pref [ i - 1 ] ^ pref [ i ]; } return ans ; } }class Solution { public: vector < int > findArray ( vector < int >& pref ) { int n = pref . size (); vector < int > ans = { pref [ 0 ]}; for ( int i = 1 ; i < n ; ++ i ) { ans . push_back ( pref [ i - 1 ] ^ pref [ i ]); } return ans ; } };class Solution : def findArray ( self , pref : List [ int ]) -> List [ int ]: return [ a ^ b for a , b in pairwise ([ 0 ] + pref )]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.