1734. Decode XORed Permutation.md

1734. Decode XORed Permutation

---

leetcode-cn Daily Challenge on May 11th, 2021.

---

Difficulty : Medium

Related Topics : Bit Manipulation

---

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

---

Solution

• mine
  • Java
    • Runtime: 2 ms, faster than 100.00%, Memory Usage: 53.8 MB, less than 64.19% of Java online submissions

      // O(N)time
      // O(N)space
      public int[] decode(int[] encoded) {
          int len = encoded.length;
          int n = len + 1;
          int[] res = new int[n];
          
          //get value of 1^2^3^...^n
          int total = 0;
          for(int i = 1; i <= n; i++){
              total ^= i;
          }
          
          //get value of res[1]^res[2]^...^res[n - 1]
          int except0 = 0;
          for(int i = 1; i < len; i += 2){
              except0 ^= encoded[i];
          }
          
          res[0] = total ^ except0;
          for(int i = 1; i < n; i++){
              res[i] = res[i - 1] ^ encoded[i - 1];
          }
          
          return res;
      }
      

---