### Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/find-the-original-array-of-prefix-xor

**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 <= 10^5
- 0 <= pref[i] <= 10^6
```

### Explanation

For an XOR operator, we have the following set of operations to be true.

```
a ^ b = c
a ^ c = b
Eg
5 ^ 7 = 2
5 ^ 2 = 7
```

We use this approach to get back our original array.

Let's check the algorithm first.

```
- set n = pref.size()
- if n == 0 || n == 1
- return pref
- loop for i = n - 1; i >= 1; i--
- pref[i] = pref[i] ^ pref[i - 1]
- return pref
```

The time complexity of the above approach is **O(n)**, and the space complexity is **O(1)**.

Let's check our algorithm in **C++**, **Golang**, and **JavaScript**.

#### C++ solution

```
class Solution {
public:
vector<int> findArray(vector<int>& pref) {
int n = pref.size();
if(n == 0 || n == 1) {
return pref;
}
for(int i = n - 1; i >= 1; i--) {
pref[i] ^= pref[i - 1];
}
return pref;
}
};
```

#### Golang solution

```
func findArray(pref []int) []int {
n := len(pref)
if n == 0 || n == 1 {
return pref
}
for i := n - 1; i >= 1; i-- {
pref[i] ^= pref[i - 1]
}
return pref
}
```

#### JavaScript solution

```
var findArray = function(pref) {
let n = pref.length;
if(n === 0 || n === 1) {
return pref;
}
for(let i = n - 1; i >= 1; i--) {
pref[i] ^= pref[i - 1];
}
return pref;
};
```

Let's dry-run our algorithm for **Example 1**.

```
Input: pref = [5, 2, 0, 3, 1]
Step 1: n = pref.size()
= 5
Step 2: if n == 0 || n == 1
5 == 0 || 5 == 1
false
Step 3: loop for i = n - 1; i >= 1; i--
i = 5 - 1 = 4
4 >= 1
true
pref[i] = pref[i] ^ pref[i - 1]
= pref[4] ^ pref[3]
= 1 ^ 3
= 2
pref = [5, 2, 0, 3, 2]
i--
i = 3
Step 4: loop for i >= 1
3 >= 1
true
pref[i] = pref[i] ^ pref[i - 1]
= pref[3] ^ pref[2]
= 3 ^ 0
= 3
pref = [5, 2, 0, 3, 2]
i--
i = 2
Step 5: loop for i >= 1
2 >= 1
true
pref[i] = pref[i] ^ pref[i - 1]
= pref[2] ^ pref[1]
= 0 ^ 2
= 2
pref = [5, 2, 2, 3, 2]
i--
i = 1
Step 6: loop for i >= 1
1 >= 1
true
pref[i] = pref[i] ^ pref[i - 1]
= pref[1] ^ pref[0]
= 2 ^ 5
= 7
pref = [5, 7, 2, 3, 2]
i--
i = 0
Step 7: loop for i >= 1
0 >= 1
false
Step 8: return pref
We return the answer as [5, 7, 2, 3, 2].
```

## Top comments (0)