LeetCode 1734. Decode XORed Permutation Solution in Java, C++, Python & Go | Explanation + Code

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 … \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],…,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).

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)