1734. Decode XORed Permutation

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

• n is odd.

• encoded.length == n - 1

Tags

Bit Manipulation

Solution

This problem is similar to but a little bit harder than LeetCode 1720. Decode XORed Array. The difference is that we do not know the first element of the target array perm. However, we can obtain this value by computing perm[:] ^ perm[1:] based on the knowledge that XOR is reversible. Given that "the array perm that is a permutation of the first n positive integers", we can formulate that perm[:] = 1 ^ 2 ^ ... ^ n. Shown in the figure above, which illustrated the relationship between encoded and perm, we know that perm[1:] = encoded[1] ^ encoded[3] ... ^ encoded[n-1]. Thus, we are able to obtain perm[0], and get the following permutation via perm[i] = perm[i-1] ^ encoded[i-1].

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func decode(encoded []int) []int {
	var total, odd int
	for i := 1; i <= len(encoded)+1; i++ {
		total ^= i
	}
	for i := 1; i < len(encoded); i += 2 {
		odd ^= encoded[i]
	}
	perm := make([]int, len(encoded)+1)
	perm[0] = total ^ odd
	for i := 1; i < len(perm); i++ {
		perm[i] = perm[i-1] ^ encoded[i-1]
	}
	return perm
}

Reference

1. 【数据结构和算法】解码异或后的排列

2. 解码异或后的排列