Skip to content

1734. Decode XORed Permutation

Description

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

Solutions

Solution 1: Bitwise Operation

We notice that the array \(perm\) is a permutation of the first \(n\) positive integers, so the XOR of all elements in \(perm\) is \(1 \oplus 2 \oplus \cdots \oplus n\), denoted as \(a\). And \(encode[i]=perm[i] \oplus perm[i+1]\), if we denote the XOR of all elements \(encode[0],encode[2],\cdots,encode[n-3]\) as \(b\), then \(perm[n-1]=a \oplus b\). Knowing the last element of \(perm\), we can find all elements of \(perm\) by traversing the array \(encode\) in reverse order.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(perm\). Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        a = b = 0
        for i in range(0, n - 1, 2):
            a ^= encoded[i]
        for i in range(1, n + 1):
            b ^= i
        perm = [0] * n
        perm[-1] = a ^ b
        for i in range(n - 2, -1, -1):
            perm[i] = encoded[i] ^ perm[i + 1]
        return perm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int a = 0, b = 0;
        for (int i = 0; i < n - 1; i += 2) {
            a ^= encoded[i];
        }
        for (int i = 1; i <= n; ++i) {
            b ^= i;
        }
        int[] perm = new int[n];
        perm[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; --i) {
            perm[i] = encoded[i] ^ perm[i + 1];
        }
        return perm;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        int a = 0, b = 0;
        for (int i = 0; i < n - 1; i += 2) {
            a ^= encoded[i];
        }
        for (int i = 1; i <= n; ++i) {
            b ^= i;
        }
        vector<int> perm(n);
        perm[n - 1] = a ^ b;
        for (int i = n - 2; ~i; --i) {
            perm[i] = encoded[i] ^ perm[i + 1];
        }
        return perm;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func decode(encoded []int) []int {
    n := len(encoded) + 1
    a, b := 0, 0
    for i := 0; i < n-1; i += 2 {
        a ^= encoded[i]
    }
    for i := 1; i <= n; i++ {
        b ^= i
    }
    perm := make([]int, n)
    perm[n-1] = a ^ b
    for i := n - 2; i >= 0; i-- {
        perm[i] = encoded[i] ^ perm[i+1]
    }
    return perm
}

Comments