1734. Decode XORed Permutation #

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.

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

Problem Summary #

Given an integer array perm, which is a permutation of the first n positive integers, and n is odd. It is encoded into another integer array encoded of length n - 1, satisfying 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 . The problem guarantees that the answer exists and is unique.

Solution Ideas #

• This problem is similar to Problem 136 and Problem 137; use the property x ^ x = 0 to solve it. According to the problem statement, the original array perm consists of n positive integers, meaning its values are in the range [1,n+1], but the permutation order is unknown. We can first XOR all numbers in the range [1,n+1] to get total. Then XOR the elements at odd indices in the encoded array to get odd:

  \[ \begin{aligned}odd &= encoded[1] + encoded[3] + ... + encoded[n-1]\\&= (perm[1] \,\, XOR \,\, perm[2]) + (perm[3] \,\,  XOR  \,\, perm[4]) + ... + (perm[n-1]  \,\, XOR \,\, perm[n])\end{aligned} \]

  total is the XOR of the complete set of n positive integers, and odd is the XOR set of n-1 positive integers. The value obtained by XORing the two, total ^ odd, must be perm[0], because x ^ x = 0, so duplicated elements disappear after being XORed. Once perm[0] is computed, the rest is easy.

  \[ \begin{aligned}encoded[0] &= perm[0] \,\, XOR \,\, perm[1]\\perm[0] \,\, XOR \,\, encoded[0] &= perm[0] \,\, XOR \,\, perm[0] \,\, XOR \,\, perm[1] = perm[1]\\perm[1] \,\, XOR \,\, encoded[1] &= perm[1] \,\, XOR \,\, perm[1] \,\, XOR \,\, perm[2] = perm[2]\\...\\perm[n-1] \,\, XOR \,\, encoded[n-1] &= perm[n-1] \,\, XOR \,\, perm[n-1] \,\, XOR \,\, perm[n] = perm[n]\\\end{aligned} \]

  Continuing this process, all numbers in the original array perm can be derived.

Code #

package leetcode

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