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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Decode XORed Permutation solution in C++
- Decode XORed Permutation solution in Java
- Decode XORed Permutation solution in Python
- Additional Resources

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
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.