LeetCode 2433: Find The Original Array of Prefix Xor

Explanation

To solve this problem, we can iterate through the given pref array and use the properties of bitwise XOR to calculate the corresponding elements of the resulting arr array. We can start by setting arr[0] = pref[0], then for each subsequent element, calculate arr[i] = pref[i] ^ arr[i-1]. The uniqueness of the solution is guaranteed by the properties of XOR operation.

Time Complexity

The time complexity of this solution is O(n) where n is the size of the pref array.

Space Complexity

The space complexity of this solution is O(n) where n is the size of the pref array.

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