Formatted question description: https://leetcode.ca/all/1720.html

# 1720. Decode XORed Array

Easy

## Description

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.

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 <= 10^4
• encoded.length == n - 1
• 0 <= encoded[i] <= 10^5
• 0 <= first <= 10^5

## Solution

Create an array arr of length n + 1 and set arr = first. Then use the property of XOR such that if a ^ b == c then there is a ^ c == b and b ^ c == a. Therefore, for each i from 0 to n - 1, there is arr[i + 1] = arr[i] ^ encoded[i]. Finally, return arr.

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