# Decode XORed Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/decode-xored-array)
Canonical: https://scaleengineer.com/dsa/problems/decode-xored-array
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
There is a **hidden** integer array `arr` that consists of `n` non-negative integers.

It was encoded into another integer array `encoded` of length `n - 1`, such that `encoded[i] = arr[i] XOR arr[i + 1]`. For example, if `arr = [1,0,2,1]`, then `encoded = [1,2,3]`.

You are given the `encoded` array. You are also given an integer `first`, that is the first element of `arr`, i.e. `arr[0]`.

Return _the original array_ `arr`. It can be proved that the answer exists and is unique.

**Example 1:**

**Input:** encoded = [1,2,3], first = 1
**Output:** [1,0,2,1]
**Explanation:** If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

**Example 2:**

**Input:** encoded = [6,2,7,3], first = 4
**Output:** [4,2,0,7,4]

**Constraints:**

* `2 <= n <= 104`
* `encoded.length == n - 1`
* `0 <= encoded[i] <= 105`
* `0 <= first <= 105`

# Approaches
## Iterative Decoding with XOR Property
The problem leverages a key property of the XOR bitwise operation: it is its own inverse. If we have `c = a XOR b`, we can find `a` by computing `c XOR b`, and we can find `b` by computing `c XOR a`.

In this problem, we are given `encoded[i] = arr[i] XOR arr[i+1]`. We are also given `arr[0]`, which is `first`. Our goal is to find `arr[1], arr[2], ..., arr[n-1]`.

Using the XOR property, we can rearrange the given equation to solve for `arr[i+1]`: `arr[i+1] = arr[i] XOR encoded[i]`.

Since we know `arr[0]`, we can calculate `arr[1]`. Once we have `arr[1]`, we can calculate `arr[2]`, and so on. This allows us to build the original array `arr` iteratively in a single pass.
**Time:** O(N), where N is the number of elements in the original array `arr`. We perform a single pass through the `encoded` array, which has N-1 elements. The work done in each iteration is constant time. · **Space:** O(N), where N is the number of elements in the original array `arr`. We need to create a result array of size N. This space is for the output and is generally considered acceptable.
**Pros:** It's a single-pass solution, making it very efficient.; The logic is straightforward and easy to understand.; It has optimal time complexity for this problem.
**Cons:** The space complexity is O(N) because a new array is created for the output. However, this is required by the problem statement and cannot be avoided.
### Explanation
This approach is a direct application of the properties of the XOR operation. We start by creating the result array, `arr`, with a size of `encoded.length + 1`.

We know the first element, so we set `arr[0] = first`.

Then, we iterate from the first element of the `encoded` array. For each `encoded[i]`, we can find the next element of our result array, `arr[i+1]`. The formula `encoded[i] = arr[i] XOR arr[i+1]` can be algebraically manipulated to `arr[i+1] = arr[i] XOR encoded[i]`. 

We loop from `i = 0` to the end of the `encoded` array. In each step, we use the previously calculated `arr[i]` and the current `encoded[i]` to find the next value `arr[i+1]`. This process continues until all elements of `arr` are decoded.

For example, with `encoded = [1,2,3]` and `first = 1`:
1. `arr` is created with size 4. `arr[0]` is set to `1`.
2. For `i=0`: `arr[1] = arr[0] ^ encoded[0] = 1 ^ 1 = 0`.
3. For `i=1`: `arr[2] = arr[1] ^ encoded[1] = 0 ^ 2 = 2`.
4. For `i=2`: `arr[3] = arr[2] ^ encoded[2] = 2 ^ 3 = 1`.

The final decoded array is `[1,0,2,1]`.

```java
class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length + 1;
        int[] arr = new int[n];
        
        // The first element of the original array is given.
        arr[0] = first;
        
        // Iterate through the encoded array to find subsequent elements.
        for (int i = 0; i < n - 1; i++) {
            // arr[i+1] = arr[i] XOR encoded[i]
            arr[i + 1] = arr[i] ^ encoded[i];
        }
        
        return arr;
    }
}
```
### Algorithm
- Create a new integer array `arr` of size `n`, where `n = encoded.length + 1`.
- Initialize the first element of the result array: `arr[0] = first`.
- Iterate through the `encoded` array from `i = 0` to `n - 2`.
- In each iteration, calculate the next element of the original array using the relationship `arr[i+1] = arr[i] XOR encoded[i]`.
- Store the result in `arr[i+1]`.
- After the loop completes, return the fully constructed `arr`.

# Solutions
### Java

```java
class Solution {
public
  int[] decode(int[] encoded, int first) {
    int n = encoded.length;
    int[] ans = new int[n + 1];
    ans[0] = first;
    for (int i = 0; i < n; ++i) {
      ans[i + 1] = ans[i] ^ encoded[i];
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]: ans = [first] for e in encoded: ans . append(ans[- 1] ^ e) return ans

```

### CPP

```cpp
class Solution {
public:
  vector<int> decode(vector<int> &encoded, int first) {
    vector<int> ans{{first}};
    for (int i = 0; i < encoded.size(); ++i)
      ans.push_back(ans[i] ^ encoded[i]);
    return ans;
  }
};

```