1734. Decode XORed Permutation

Medium

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 < 10^5

• n is odd.

• encoded.length == n - 1

解題

func decode(encoded []int) []int {
    // perm[i] = perm[i – 1] ^ encoded[i – 1]
    // 1. p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
    // 2. encoded[1] ^ encode[3] ^ … ^ encoded[n-2] = (p[1] ^ p[2]) ^ (p[3] ^ p[4]) ^ … ^ (p[n-2] ^ p[n-1])
    // 1. xor 2. = p[0]
    // now we can calculate perm[i] = perm[i – 1] ^ encoded[i – 1] from i = 1

    sum := 0

    for i := 1; i <= len(encoded) + 1; i++ {
        sum ^= i
    }

    nohead := 0
    for i := 1; i < len(encoded); i+=2 {
        nohead ^= encoded[i]
    }

    head := nohead ^ sum
    ans := make([]int, 0)
    ans = append(ans, head)

    for i := 1; i < len(encoded) + 1; i++ {
        ans = append(ans, ans[i-1]^encoded[i-1])
    }

    return ans
}