[LeetCode] 1734. Decode XORed Permutation

- Problem

1734. Decode XORed Permutation

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

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

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Example 1:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

Constraints:

- 3 <= n < 105
- n is odd.
- encoded.length == n - 1

- 내 풀이 1

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        xor_all_number = reduce(lambda x, y : x ^ y, list(range(1, n+1)))
        xor_except_last_number = reduce(lambda x, y : x ^ y, list(encoded[::2]))
        result = [xor_all_number ^ xor_except_last_number]
        
        for encode in encoded[::-1]:
            result.append(result[-1] ^ encode)
        
        return result[::-1]

- 내 풀이 2

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        xor_except_last_number, xor_first_last_number = 0, 0
        xor_all_number = reduce(lambda x, y : x ^ y, range(1, n+1))
        
        for i, v in enumerate(encoded):
            if i % 2 == 0:
                xor_except_last_number ^= v
            xor_first_last_number ^= v
        result = [xor_first_last_number ^ xor_all_number ^ xor_except_last_number]
        
        for encode in encoded:
            result.append(result[-1] ^ encode)
        
        return result

- 내 풀이 3

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        xor_all_number = reduce(lambda x, y : x ^ y, range(1, len(encoded) + 2))
        xor_except_first_number = reduce(lambda x, y : x ^ y, encoded[1::2])
        
        result = [xor_all_number ^ xor_except_first_number]
        
        for encode in encoded:
            result.append(result[-1] ^ encode)
        
        return result

- 결과