LeetCode 1734: Decode XORed Permutation

Explanation

To decode the XORed permutation, we need to find the original permutation array perm given the encoded array. Since perm is a permutation of the first n positive integers, we know that perm can be derived by XORing all elements from 1 to n. By using the properties of XOR operation, we can find the first element of perm and then calculate the rest of the elements iteratively.

1. Find the XOR of all elements from 1 to n.
2. Find the XOR of all elements in the encoded array.
3. XOR the result of step 1 with the result of step 2 to get the first element of perm.
4. Iterate through the encoded array to find the rest of the elements of perm.

Time Complexity: O(n) where n is the length of the encoded array.

Space Complexity: O(n) for storing the decoded permutation.

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