1734. Decode XORed Permutation LeetCode Solution

In this guide, you will get 1734. Decode XORed Permutation LeetCode Solution with the best time and space complexity. The solution to Decode XORed Permutation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Decode XORed Permutation solution in C++
Decode XORed Permutation solution in Java
Decode XORed Permutation solution in Python
Additional Resources

1734. Decode XORed Permutation LeetCode Solution image

Problem Statement of Decode XORed Permutation

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1734. Decode XORed Permutation LeetCode Solution in C++

class Solution {
 public:
  vector<int> decode(vector<int>& encoded) {
    // Our goal is to find the value of a1, which will allow us to decode a2,
    // a3, ..., an. This can be achieved by performing XOR operation between
    // each element in `encoded` and a1.
    //
    // e.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3]
    //               encoded = [a1^a2, a2^a3]
    //    accumulatedEncoded = [a1^a2, a1^a3]
    //    a1 = (a1^a2)^(a1^a3)^(a1^a2^a3)
    //    a2 = a1^(a1^a2)
    //    a3 = a2^(a2^a3)
    const int n = encoded.size() + 1;
    int nXors = 0;
    for (int i = 1; i <= n; i++)
      nXors ^= i;

    // Instead of constructing the array, we can track of the running XOR value
    // of `accumulatedEncoded`.
    int runningXors = 0;
    int xors = 0;  // xors(accumulatedEncoded)

    for (const int encode : encoded) {
      runningXors ^= encode;
      xors ^= runningXors;
    }

    vector<int> ans{xors ^ nXors};

    for (const int encode : encoded)
      ans.push_back(ans.back() ^ encode);

    return ans;
  }
};
/* code provided by PROGIEZ */

1734. Decode XORed Permutation LeetCode Solution in Java

class Solution {
  public int[] decode(int[] encoded) {
    // Our goal is to find the value of a1, which will allow us to decode a2,
    // a3, ..., an. This can be achieved by performing XOR operation between
    // each element in `encoded` and a1.
    //
    // e.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3]
    //               encoded = [a1^a2, a2^a3]
    //    accumulatedEncoded = [a1^a2, a1^a3]
    //    a1 = (a1^a2)^(a1^a3)^(a1^a2^a3)
    //    a2 = a1^(a1^a2)
    //    a3 = a2^(a2^a3)
    final int n = encoded.length + 1;
    int nXors = 0;
    for (int i = 1; i <= n; i++)
      nXors ^= i;

    // Instead of constructing the array, we can track of the running XOR value
    // of `accumulatedEncoded`.
    int runningXors = 0;
    int xors = 0; // xors(accumulatedEncoded)

    for (final int encode : encoded) {
      runningXors ^= encode;
      xors ^= runningXors;
    }

    int[] ans = new int[encoded.length + 1];
    ans[0] = xors ^ nXors;

    for (int i = 0; i < encoded.length; i++)
      ans[i + 1] = ans[i] ^ encoded[i];

    return ans;
  }
}
// code provided by PROGIEZ

1734. Decode XORed Permutation LeetCode Solution in Python

class Solution:
  def decode(self, encoded: list[int]) -> list[int]:
    # Our goal is to find the value of a1, which will allow us to decode a2, a3,
    # ..., an. This can be achieved by performing XOR operation between each
    # element in `encoded` and a1.
    #
    # e.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3].
    #               encoded = [a1^a2, a2^a3]
    #    accumulatedEncoded = [a1^a2, a1^a3]
    #    a1 = (a1^a2)^(a1^a3)^(a1^a2^a3)
    #    a2 = a1^(a1^a2)
    #    a3 = a2^(a2^a3)
    n = len(encoded) + 1
    nXors = functools.reduce(operator.xor, [i for i in range(1, n + 1)])

    # Instead of constructing the array, we can track of the running XOR value
    # of `accumulatedEncoded`.
    xors = 0  # xors(accumulatedEncoded)

    for encode in encoded:
      runningXors ^= encode
      xors ^= runningXors

    ans = [xors ^ nXors]

    for encode in encoded:
      ans.append(ans[-1] ^ encode)

    return ans
 # code by PROGIEZ