Facebook Pixel

1734. Decode XORed Permutation

MediumBit ManipulationArray
Leetcode Link

Problem Description

You are given an integer array encoded that was created from a hidden array perm. The array perm is a permutation of the first n positive integers (1, 2, 3, ..., n), where n is always odd.

The encoding process works as follows: each element in encoded is the XOR of two consecutive elements in perm. Specifically, encoded[i] = perm[i] XOR perm[i + 1] for all valid indices. The encoded array has length n - 1 since it represents the XOR operations between consecutive pairs.

For example:

  • If perm = [1, 3, 2], then encoded = [2, 1] because:
    • encoded[0] = perm[0] XOR perm[1] = 1 XOR 3 = 2
    • encoded[1] = perm[1] XOR perm[2] = 3 XOR 2 = 1

Your task is to decode the encoded array and return the original perm array. The problem guarantees that there exists a unique solution.

The key insight is that since perm contains all integers from 1 to n exactly once, and n is odd, you can use XOR properties to determine one element of perm. Once you know one element, you can reconstruct the entire array using the relationship perm[i] = encoded[i] XOR perm[i + 1] (working backwards) or perm[i + 1] = encoded[i] XOR perm[i] (working forwards).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The challenge is that we have n-1 equations (from the encoded array) but n unknowns (the elements of perm). We need one more piece of information to solve this system.

Let's think about what we know:

  1. perm contains all integers from 1 to n exactly once
  2. n is always odd
  3. encoded[i] = perm[i] XOR perm[i+1]

The key observation is that we can use the XOR property where a XOR a = 0 and a XOR 0 = a. Since perm is a permutation of 1 to n, we know that perm[0] XOR perm[1] XOR ... XOR perm[n-1] = 1 XOR 2 XOR ... XOR n.

Now, let's look at the pattern when we XOR alternate elements of the encoded array:

  • encoded[0] = perm[0] XOR perm[1]
  • encoded[2] = perm[2] XOR perm[3]
  • encoded[4] = perm[4] XOR perm[5]
  • ...
  • encoded[n-3] = perm[n-3] XOR perm[n-2]

If we XOR all these alternate elements (starting from index 0), we get: encoded[0] XOR encoded[2] XOR ... XOR encoded[n-3] = perm[0] XOR perm[1] XOR perm[2] XOR ... XOR perm[n-2]

This gives us the XOR of all elements in perm except the last one (perm[n-1]).

Since we know the XOR of all elements in perm is 1 XOR 2 XOR ... XOR n, and we just calculated the XOR of all elements except the last one, we can find the last element: perm[n-1] = (1 XOR 2 XOR ... XOR n) XOR (perm[0] XOR perm[1] XOR ... XOR perm[n-2])

Once we know perm[n-1], we can work backwards using the encoded array. Since encoded[i] = perm[i] XOR perm[i+1], we can rearrange to get perm[i] = encoded[i] XOR perm[i+1]. Starting from the known perm[n-1], we can find perm[n-2], then perm[n-3], and so on, until we reconstruct the entire array.

Solution Approach

The implementation follows the intuition we developed:

Step 1: Calculate the XOR of all elements except the last one

We iterate through the encoded array at alternate positions (indices 0, 2, 4, ..., n-3) and XOR them together:

a = 0
for i in range(0, n - 1, 2):
    a ^= encoded[i]

This gives us a = perm[0] XOR perm[1] XOR ... XOR perm[n-2].

Step 2: Calculate the XOR of all integers from 1 to n

Since perm is a permutation of integers 1 to n, we calculate:

b = 0
for i in range(1, n + 1):
    b ^= i

This gives us b = 1 XOR 2 XOR ... XOR n = perm[0] XOR perm[1] XOR ... XOR perm[n-1].

Step 3: Find the last element of perm

Using XOR properties, we can isolate the last element:

perm[-1] = a ^ b

This works because a ^ b = (perm[0] XOR ... XOR perm[n-2]) XOR (perm[0] XOR ... XOR perm[n-1]). Due to the XOR property where x XOR x = 0, all elements except perm[n-1] cancel out, leaving us with just perm[n-1].

Step 4: Reconstruct the entire perm array backwards

Now that we know perm[n-1], we can work backwards using the relationship perm[i] = encoded[i] XOR perm[i+1]:

perm = [0] * n
perm[-1] = a ^ b  # Set the last element
for i in range(n - 2, -1, -1):
    perm[i] = encoded[i] ^ perm[i + 1]

Starting from index n-2 and moving backwards to index 0, we calculate each element of perm using the encoded value and the already-known next element.

The time complexity is O(n) as we iterate through the arrays a constant number of times. The space complexity is O(n) for storing the result array perm.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with encoded = [6, 5, 4, 6].

Since encoded has length 4, we know that n = 5 (the original perm array has 5 elements), and perm is a permutation of [1, 2, 3, 4, 5].

Step 1: Calculate XOR of all elements except the last one

We XOR alternate elements of encoded starting from index 0:

  • Indices to XOR: 0, 2 (skip odd indices)
  • a = encoded[0] XOR encoded[2] = 6 XOR 4 = 2

This value represents perm[0] XOR perm[1] XOR perm[2] XOR perm[3] (all elements except the last).

Step 2: Calculate XOR of all integers from 1 to n

We XOR all integers from 1 to 5:

  • b = 1 XOR 2 XOR 3 XOR 4 XOR 5
  • b = 1 XOR 2 = 3, then 3 XOR 3 = 0, then 0 XOR 4 = 4, then 4 XOR 5 = 1
  • So b = 1

This represents the XOR of all elements in the complete perm array.

Step 3: Find the last element of perm

Using the values from steps 1 and 2:

  • perm[4] = a XOR b = 2 XOR 1 = 3

Now we know the last element of perm is 3.

Step 4: Reconstruct the entire array backwards

Starting from perm[4] = 3, we work backwards using perm[i] = encoded[i] XOR perm[i+1]:

  • perm[3] = encoded[3] XOR perm[4] = 6 XOR 3 = 5
  • perm[2] = encoded[2] XOR perm[3] = 4 XOR 5 = 1
  • perm[1] = encoded[1] XOR perm[2] = 5 XOR 1 = 4
  • perm[0] = encoded[0] XOR perm[1] = 6 XOR 4 = 2

Therefore, perm = [2, 4, 1, 5, 3].

Verification: Let's verify this is correct by checking if it produces our original encoded array:

  • perm[0] XOR perm[1] = 2 XOR 4 = 6 ✓ (matches encoded[0])
  • perm[1] XOR perm[2] = 4 XOR 1 = 5 ✓ (matches encoded[1])
  • perm[2] XOR perm[3] = 1 XOR 5 = 4 ✓ (matches encoded[2])
  • perm[3] XOR perm[4] = 5 XOR 3 = 6 ✓ (matches encoded[3])

And indeed, [2, 4, 1, 5, 3] is a valid permutation of [1, 2, 3, 4, 5].

Solution Implementation

1class Solution:
2    def decode(self, encoded: List[int]) -> List[int]:
3        # Calculate the length of the original permutation
4        # Since encoded has n-1 elements, the permutation has n elements
5        n = len(encoded) + 1
6      
7        # Calculate XOR of elements at even indices in encoded array
8        # This represents: perm[0] ^ perm[1] ^ perm[2] ^ perm[3] ^ ... (excluding last element)
9        xor_even_indices = 0
10        for i in range(0, n - 1, 2):
11            xor_even_indices ^= encoded[i]
12      
13        # Calculate XOR of all numbers from 1 to n
14        # Since perm is a permutation of [1, 2, ..., n], this gives us XOR of all elements
15        xor_all_numbers = 0
16        for i in range(1, n + 1):
17            xor_all_numbers ^= i
18      
19        # Initialize the result permutation array
20        permutation = [0] * n
21      
22        # Find the last element of the permutation
23        # xor_even_indices gives us XOR of all elements except the last one
24        # xor_all_numbers ^ xor_even_indices cancels out all except the last element
25        permutation[-1] = xor_even_indices ^ xor_all_numbers
26      
27        # Reconstruct the permutation from right to left
28        # Since encoded[i] = permutation[i] ^ permutation[i+1]
29        # We can get permutation[i] = encoded[i] ^ permutation[i+1]
30        for i in range(n - 2, -1, -1):
31            permutation[i] = encoded[i] ^ permutation[i + 1]
32      
33        return permutation
34
1class Solution {
2    public int[] decode(int[] encoded) {
3        // Calculate the length of the original permutation
4        // Since encoded array has n-1 elements, the original has n elements
5        int permutationLength = encoded.length + 1;
6      
7        // XOR of elements at even indices in the encoded array
8        // This will give us XOR of all elements except the last one in the permutation
9        int xorOfEvenIndices = 0;
10        for (int i = 0; i < permutationLength - 1; i += 2) {
11            xorOfEvenIndices ^= encoded[i];
12        }
13      
14        // XOR of all numbers from 1 to n (the complete permutation)
15        int xorOfAllNumbers = 0;
16        for (int i = 1; i <= permutationLength; i++) {
17            xorOfAllNumbers ^= i;
18        }
19      
20        // Initialize the result array to store the decoded permutation
21        int[] decodedPermutation = new int[permutationLength];
22      
23        // Calculate the last element of the permutation
24        // xorOfEvenIndices contains XOR of all elements except the last
25        // xorOfAllNumbers contains XOR of all elements
26        // Therefore, xorOfEvenIndices ^ xorOfAllNumbers gives us the last element
27        decodedPermutation[permutationLength - 1] = xorOfEvenIndices ^ xorOfAllNumbers;
28      
29        // Reconstruct the permutation from right to left
30        // Using the property: encoded[i] = permutation[i] ^ permutation[i+1]
31        // Therefore: permutation[i] = encoded[i] ^ permutation[i+1]
32        for (int i = permutationLength - 2; i >= 0; i--) {
33            decodedPermutation[i] = encoded[i] ^ decodedPermutation[i + 1];
34        }
35      
36        return decodedPermutation;
37    }
38}
39
1class Solution {
2public:
3    vector<int> decode(vector<int>& encoded) {
4        // Calculate the size of the original permutation
5        // Since encoded has n-1 elements, the permutation has n elements
6        int n = encoded.size() + 1;
7      
8        // Calculate XOR of elements at even indices in encoded array
9        // This gives us XOR of odd-indexed elements in the permutation (except the last)
10        // encoded[0] = perm[0] ^ perm[1], encoded[2] = perm[2] ^ perm[3], ...
11        int xorOfOddPositions = 0;
12        for (int i = 0; i < n - 1; i += 2) {
13            xorOfOddPositions ^= encoded[i];
14        }
15      
16        // Calculate XOR of all numbers from 1 to n
17        // Since permutation contains all numbers from 1 to n exactly once
18        int xorOfAllNumbers = 0;
19        for (int i = 1; i <= n; ++i) {
20            xorOfAllNumbers ^= i;
21        }
22      
23        // Initialize the result permutation array
24        vector<int> permutation(n);
25      
26        // Find the last element of the permutation
27        // xorOfOddPositions contains XOR of all odd-positioned elements except the last
28        // xorOfAllNumbers contains XOR of all elements
29        // Therefore, last element = xorOfOddPositions ^ xorOfAllNumbers
30        permutation[n - 1] = xorOfOddPositions ^ xorOfAllNumbers;
31      
32        // Reconstruct the permutation backwards using the encoded array
33        // Since encoded[i] = permutation[i] ^ permutation[i+1]
34        // We can derive: permutation[i] = encoded[i] ^ permutation[i+1]
35        for (int i = n - 2; i >= 0; --i) {
36            permutation[i] = encoded[i] ^ permutation[i + 1];
37        }
38      
39        return permutation;
40    }
41};
42
1function decode(encoded: number[]): number[] {
2    // Calculate the size of the original permutation
3    // Since encoded has n-1 elements, the permutation has n elements
4    const n: number = encoded.length + 1;
5  
6    // Calculate XOR of elements at even indices in encoded array
7    // This gives us XOR of odd-indexed elements in the permutation (except the last)
8    // encoded[0] = perm[0] ^ perm[1], encoded[2] = perm[2] ^ perm[3], ...
9    let xorOfOddPositions: number = 0;
10    for (let i = 0; i < n - 1; i += 2) {
11        xorOfOddPositions ^= encoded[i];
12    }
13  
14    // Calculate XOR of all numbers from 1 to n
15    // Since permutation contains all numbers from 1 to n exactly once
16    let xorOfAllNumbers: number = 0;
17    for (let i = 1; i <= n; i++) {
18        xorOfAllNumbers ^= i;
19    }
20  
21    // Initialize the result permutation array
22    const permutation: number[] = new Array(n);
23  
24    // Find the last element of the permutation
25    // xorOfOddPositions contains XOR of all odd-positioned elements except the last
26    // xorOfAllNumbers contains XOR of all elements
27    // Therefore, last element = xorOfOddPositions ^ xorOfAllNumbers
28    permutation[n - 1] = xorOfOddPositions ^ xorOfAllNumbers;
29  
30    // Reconstruct the permutation backwards using the encoded array
31    // Since encoded[i] = permutation[i] ^ permutation[i+1]
32    // We can derive: permutation[i] = encoded[i] ^ permutation[i+1]
33    for (let i = n - 2; i >= 0; i--) {
34        permutation[i] = encoded[i] ^ permutation[i + 1];
35    }
36  
37    return permutation;
38}
39

Time and Space Complexity

The time complexity is O(n), where n is the length of the array perm (which equals len(encoded) + 1).

Breaking down the time complexity:

  • The first loop iterates through the encoded array with step 2, performing O(n/2) XOR operations, which is O(n).
  • The second loop iterates from 1 to n+1, performing n XOR operations, which is O(n).
  • The third loop iterates from n-2 to 0, performing n-1 XOR operations, which is O(n).
  • Overall: O(n) + O(n) + O(n) = O(n).

The space complexity is O(n) for the output array perm. However, if we ignore the space consumption of the answer (as mentioned in the reference), the space complexity is O(1), since we only use a constant amount of extra space for variables a, b, i, and n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect XOR Pattern Selection

Pitfall: A common mistake is choosing the wrong indices when calculating the XOR of encoded elements. Developers might accidentally XOR elements at odd indices (1, 3, 5, ...) instead of even indices (0, 2, 4, ...), or vice versa.

Why it happens: The relationship between consecutive XOR operations can be confusing. When we have encoded[i] = perm[i] ^ perm[i+1], the pattern of which elements cancel out when XORing alternating encoded values isn't immediately obvious.

Solution: Remember that:

  • XORing encoded elements at even indices (0, 2, 4, ...) gives you perm[0] ^ perm[n-1]
  • XORing encoded elements at odd indices (1, 3, 5, ...) gives you perm[1] ^ perm[n-1]

Since we need to isolate perm[n-1], and we know the XOR of all elements (1 to n), using even indices is correct because it includes perm[0] which allows us to use all elements except perm[n-1] in our calculation.

2. Off-by-One Errors in Array Length Calculation

Pitfall: Confusing the relationship between the lengths of encoded and perm arrays. Some might incorrectly assume n = len(encoded) instead of n = len(encoded) + 1.

Why it happens: The problem states that encoded has n-1 elements where n is the length of the permutation, but it's easy to mix up which variable represents which length.

Solution: Always remember:

  • If perm has n elements
  • Then encoded has n-1 elements (one less because it represents pairs)
  • Therefore, n = len(encoded) + 1

3. Attempting to Reconstruct from the Wrong Direction

Pitfall: Trying to reconstruct the permutation from left to right when you've found the last element, or from right to left when you've found the first element, leading to dependency issues.

Why it happens: The reconstruction formula perm[i] = encoded[i] ^ perm[i+1] requires knowing perm[i+1] to find perm[i]. If you've found perm[n-1] but try to reconstruct from index 0 forward, you'll get stuck.

Solution: Match your reconstruction direction with the element you've found:

  • If you found perm[n-1] (last element): Reconstruct backwards from index n-2 to 0
  • If you found perm[0] (first element): Reconstruct forwards from index 1 to n-1

The formula changes accordingly:

  • Backwards: perm[i] = encoded[i] ^ perm[i+1]
  • Forwards: perm[i+1] = encoded[i] ^ perm[i]
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More