LeetCode 1720: Decode XORed Array

Explanation

To decode the XORed array, we need to reverse the process of XOR operation. Given the encoded array and the first element of the original array, we can reconstruct the original array by iteratively XORing the elements in the encoded array with the elements of the original array.

1. Initialize an array arr of size n with the first element as first.
2. Iterate through the encoded array from index 0 to n-2.
3. Calculate each element in the original array by XORing the corresponding element in the encoded array with the previous element in the original array.

Time complexity: O(n) where n is the size of the array. Space complexity: O(n) for the output array.

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