Decode XORed Permutation solution and explanation
9 more videos on this problem
Leetcode 1734. Decode XORed PermutationFraz · 19:56 · 2K views
Decode XORed Permutation | Leetcode #1734Techdose · 12:26 · 1K views
Decode XORed Permutation | 1734 | Leetcode Biweekly Contest | Bit ManipulationAnmol Gera · 8:19 · 776 views
LeetCode 1734. Decode XORed PermutationHappy Coding · 15:26 · 476 views
1734. Decode XORed Permutation | LEETCODE MEDIUM | XOR | BIT MANIPULATIONcode Explainer · 10:07 · 449 views
1734. Decode XORed Permutation (Leetcode Medium)Programming Live with Larry · 6:24 · 424 views
【每日一题】1734. Decode XORed Permutation, 1/23/2021Huifeng Guan · 8:46 · 348 views
Leetcode 1734. Decode Xored Permutation (Biweekly Contest 44)Runtime Terrors · 5:49 · 173 views
1734. Decode XORed Permutation (Solution Explained) | LeetCode | BitWise: #07Akshay Anil · 13:52 · 159 views
Bit Manipulation 13. Decode XORed Permutation | AlgoMaster Sheet | Leetcode 1734 |CS FOR ALL · 15:52 · 105 views
The problem
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 < 105nis odd.encoded.length == n - 1
Approach overview
Problem Overview: You receive an array encoded where encoded[i] = perm[i] XOR perm[i+1]. The original array perm is a permutation of numbers from 1 to n and n is odd. The task is to reconstruct the entire permutation. The challenge is recovering the first element efficiently using XOR properties.
Approach 1: Brute Force Guessing (O(n^2) time, O(1) space)
One direct idea is to try every possible value from 1 to n as the first element of the permutation. Once the first element is fixed, the rest of the array can be reconstructed because perm[i+1] = perm[i] XOR encoded[i]. After generating the candidate permutation, verify whether it forms a valid permutation containing every number from 1 to n exactly once. This works because XOR uniquely determines the next element when the previous value is known. However, validating permutations repeatedly pushes the complexity to O(n^2), which is unnecessary given the constraints.
Approach 2: Determine Total XOR (O(n) time, O(1) space)
The optimal strategy relies on XOR properties and the fact that the array is a permutation of 1..n. First compute the XOR of all numbers from 1 to n. This represents perm[0] XOR perm[1] XOR ... XOR perm[n-1]. Next, compute the XOR of all elements at odd indices in encoded (encoded[1] ^ encoded[3] ^ ...). Expanding these terms cancels many values and leaves perm[1] XOR perm[2] XOR ... XOR perm[n-1].
Now XOR the two results. The overlapping elements cancel out, leaving only perm[0]. Once the first value is known, reconstruct the rest of the permutation by iterating through the encoded array and applying perm[i+1] = perm[i] ^ encoded[i]. This approach performs a few linear passes over the array and uses constant extra memory.
This technique works because XOR is associative and self-inverting (a ^ a = 0). Those properties allow large portions of the permutation to cancel out during aggregation. Problems like this often appear in Bit Manipulation practice and combine XOR tricks with simple iteration over an Array. The reconstruction step is essentially a forward pass similar to computing values from a prefix XOR relationship.
Recommended for interviews: The total XOR method is the expected solution. Interviewers want to see that you recognize XOR cancellation and use the permutation constraint to recover the first element. Mentioning the brute force idea shows reasoning, but deriving the O(n) XOR trick demonstrates strong problem-solving skills.
Approach 1: Approach 1: Determine Total XOR
This method utilizes the properties of XOR to find the first element of the permutation. Since perm is a permutation of the first n positive integers, compute the total XOR of numbers from 1 to n. Calculate the XOR of the encoded array at every alternate index (odd positions really give us the XOR excluding perm[0]). The difference gives us the first element of perm, and from there, remaining permutation elements can be deduced.
def decode(encoded):
n = len(encoded) + 1
total_xor = 0
for i in range(1, n + 1):
total_xor ^= i
odd_index_xor = 0
for i in range(1, len(encoded), 2):
odd_index_xor ^= encoded[i]
first_element = total_xor ^ odd_index_xor
perm = [first_element]
for num in encoded:
perm.append(perm[-1] ^ num)
return permimport java.util.*;
public class Decode {
public static int[] decode(int[] encoded) {
int n = encoded.length + 1;
int total_xor = 0;
for (int i = 1; i <= n; ++i) {
total_xor ^= i;
}
int odd_index_xor = 0;
for (int i = 1; i < encoded.length; i += 2) {
odd_index_xor ^= encoded[i];
}
int first_element = total_xor ^ odd_index_xor;
int[] perm = new int[n];
perm[0] = first_element;
for (int i = 0; i < encoded.length; ++i) {
perm[i + 1] = perm[i] ^ encoded[i];
}
return perm;
}
}#include <vector>
std::vector<int> decode(std::vector<int>& encoded) {
int n = encoded.size() + 1;
int total_xor = 0;
for (int i = 1; i <= n; ++i) {
total_xor ^= i;
}
int odd_index_xor = 0;
for (int i = 1; i < encoded.size(); i += 2) {
odd_index_xor ^= encoded[i];
}
int first_element = total_xor ^ odd_index_xor;
std::vector<int> perm;
perm.push_back(first_element);
for (int num : encoded) {
perm.push_back(perm.back() ^ num);
}
return perm;
}function decode(encoded) {
const n = encoded.length + 1;
let total_xor = 0;
for (let i = 1; i <= n; ++i) {
total_xor ^= i;
}
let odd_index_xor = 0;
for (let i = 1; i < encoded.length; i += 2) {
odd_index_xor ^= encoded[i];
}
let first_element = total_xor ^ odd_index_xor;
const perm = [first_element];
for (let num of encoded) {
perm.push(perm[perm.length - 1] ^ num);
}
return perm;
}#include <stdio.h>
void decode(int* encoded, int encodedSize, int* returnArray, int* returnSize) {
int n = encodedSize + 1;
int total_xor = 0;
for (int i = 1; i <= n; ++i) {
total_xor ^= i;
}
int odd_index_xor = 0;
for (int i = 1; i < encodedSize; i += 2) {
odd_index_xor ^= encoded[i];
}
int first_element = total_xor ^ odd_index_xor;
returnArray[0] = first_element;
for (int i = 0; i < encodedSize; ++i) {
returnArray[i + 1] = returnArray[i] ^ encoded[i];
}
*returnSize = n;
}using System;
public class Solution {
public int[] Decode(int[] encoded) {
int n = encoded.Length + 1;
int total_xor = 0;
for (int i = 1; i <= n; ++i) {
total_xor ^= i;
}
int odd_index_xor = 0;
for (int i = 1; i < encoded.Length; i += 2) {
odd_index_xor ^= encoded[i];
}
int first_element = total_xor ^ odd_index_xor;
int[] perm = new int[n];
perm[0] = first_element;
for (int i = 0; i < encoded.Length; ++i) {
perm[i + 1] = perm[i] ^ encoded[i];
}
return perm;
}
}The solution first calculates the XOR of all numbers from 1 to n. It then computes the XOR of encoded elements at odd indices which helps in isolating perm[0]. Next, it computes the first element using XOR properties. Subsequently, it utilizes a loop to deduce perm from encoded.
Time Complexity: O(n), as there are two traversals over the arrays. Space Complexity: O(1), excluding the space needed for the output.
Approach 2: 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).
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Determine Total XOR | Time Complexity: O(n), as there are two traversals over the arrays. Space Complexity: O(1), excluding the space needed for the output. |
| Bitwise Operation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Guess First Element | O(n^2) | O(1) | Conceptual baseline to understand reconstruction from XOR relations |
| Determine Total XOR (Optimal) | O(n) | O(1) | General case. Uses XOR properties and permutation constraint for optimal decoding |
Frequently asked questions
Is Decode XORed Permutation easy or hard?
Decode XORed Permutation is rated Medium because the reconstruction step is simple but identifying the XOR trick requires insight. Once the XOR cancellation property and permutation constraint are recognized, the implementation becomes straightforward.
Decode XORed Permutation Python/Java solution
Python and Java implementations follow the same logic: compute total XOR from 1..n, compute XOR of encoded at odd indices, derive the first permutation value, then build the rest using perm[i+1] = perm[i] ^ encoded[i]. Both implementations run in O(n) time with constant extra memory.
How to solve Decode XORed Permutation in O(n)?
First compute the XOR of all numbers from 1 through n. Then compute the XOR of encoded values at odd indices. XORing these two results gives the first element of the permutation. With the first element known, reconstruct the rest by iterating once through encoded using perm[i+1] = perm[i] ^ encoded[i].
What is the best approach for Decode XORed Permutation?
The best approach computes the XOR of all numbers from 1 to n and combines it with the XOR of encoded elements at odd indices. This reveals the first element of the permutation using XOR cancellation. After that, reconstruct the rest with perm[i+1] = perm[i] ^ encoded[i]. The algorithm runs in O(n) time and O(1) extra space.
Is Decode XORed Permutation asked at Google/Amazon/Meta?
XOR reconstruction and permutation recovery problems appear in interviews at companies like Google, Amazon, and Meta when testing bit manipulation fundamentals. The exact problem may vary, but the XOR cancellation pattern and permutation constraints are common interview themes.
What data structure is used in Decode XORed Permutation?
The problem mainly uses arrays and bit manipulation techniques. No advanced data structures are required. The key operations involve iterating through arrays and applying XOR to reconstruct values.
What is the time complexity of Decode XORed Permutation?
The optimal solution runs in O(n) time because it performs a few linear passes over the encoded array. Computing the XOR of numbers from 1 to n and iterating through encoded each take O(n). Space complexity remains O(1) since only a few variables are stored.