Welcome to Subscribe On Youtube

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)$.

• Java
• C++
• Python
• Go

• 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;
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  

All Problems

All Solutions