Problem

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.

Examples

Example 1

1
2
3

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

1
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

Solution

Method 1 – XOR Properties and Prefix XOR

Intuition

The encoded array is formed by XORing consecutive elements of a permutation of the first n positive integers. Since n is odd, we can use the properties of XOR to recover the original permutation. The key is that XOR-ing all numbers from 1 to n and all encoded values in a certain pattern allows us to deduce the first element, and then reconstruct the rest.

Approach

  1. Let n = len(encoded) + 1.
  2. Compute total as the XOR of all numbers from 1 to n (i.e., 1^2^…^n).
  3. Compute odd as the XOR of all encoded elements at odd indices (i.e., encoded[1], encoded[3], …).
  4. The first element of perm is first = total ^ odd.
  5. Reconstruct the rest of perm by iteratively XORing the previous value with the corresponding encoded value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

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

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int total = 0;
        for (int i = 1; i <= n; i++) total ^= i;
        int odd = 0;
        for (int i = 1; i < n - 1; i += 2) odd ^= encoded[i];
        int[] ans = new int[n];
        ans[0] = total ^ odd;
        for (int i = 0; i < n - 1; i++) {
            ans[i + 1] = ans[i] ^ encoded[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun decode(encoded: IntArray): IntArray {
        val n = encoded.size + 1
        var total = 0
        for (i in 1..n) total = total xor i
        var odd = 0
        for (i in 1 until n - 1 step 2) odd = odd xor encoded[i]
        val ans = IntArray(n)
        ans[0] = total xor odd
        for (i in 0 until n - 1) {
            ans[i + 1] = ans[i] xor encoded[i]
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def decode(self, encoded: list[int]) -> list[int]:
        n: int = len(encoded) + 1
        total: int = 0
        for i in range(1, n + 1):
            total ^= i
        odd: int = 0
        for i in range(1, n - 1, 2):
            odd ^= encoded[i]
        ans: list[int] = [0] * n
        ans[0] = total ^ odd
        for i in range(n - 1):
            ans[i + 1] = ans[i] ^ encoded[i]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn decode(encoded: Vec<i32>) -> Vec<i32> {
        let n = encoded.len() + 1;
        let mut total = 0;
        for i in 1..=n as i32 {
            total ^= i;
        }
        let mut odd = 0;
        for i in (1..n - 1).step_by(2) {
            odd ^= encoded[i];
        }
        let mut ans = vec![0; n];
        ans[0] = total ^ odd;
        for i in 0..n - 1 {
            ans[i + 1] = ans[i] ^ encoded[i];
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    decode(encoded: number[]): number[] {
        const n = encoded.length + 1;
        let total = 0;
        for (let i = 1; i <= n; i++) total ^= i;
        let odd = 0;
        for (let i = 1; i < n - 1; i += 2) odd ^= encoded[i];
        const ans = new Array(n);
        ans[0] = total ^ odd;
        for (let i = 0; i < n - 1; i++) {
            ans[i + 1] = ans[i] ^ encoded[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the permutation, since we process each element a constant number of times.
  • 🧺 Space complexity: O(n), for the answer array of size n.