# Find The Original Array of Prefix Xor
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-original-array-of-prefix-xor)
Canonical: https://scaleengineer.com/dsa/problems/find-the-original-array-of-prefix-xor
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## Problem
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 <= 105`
* `0 <= pref[i] <= 106`

# Approaches
## Brute-Force with Re-computation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a new integer array `arr` of the same size as `pref`.
- If `pref` is not empty, set `arr[0] = pref[0]`.
- Iterate with a loop from `i = 1` to `pref.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`.

## Single-Pass with Extra Space
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a result array `arr` of size `n`.
- Handle the base case: `arr[0] = pref[0]`.
- Iterate from `i = 1` to `n-1`.
- For each `i`, apply the formula: `arr[i] = pref[i-1] ^ pref[i]`.
- Return `arr`.

## In-Place Single-Pass (Optimal)
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Iterate from the end of the array to the second element, i.e., from `i = n-1` down to `1`.
- 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, as `arr[0] = pref[0]`, so it's left untouched.
- Return the modified `pref` array.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
class Solution : def findArray ( self , pref : List [ int ]) -> List [ int ]: return [ a ^ b for a , b in pairwise ([ 0 ] + pref )]
```