1734. Decode XORed Permutation

MediumBit ManipulationArray
Leetcode Link

Problem Description

There is an array perm which is a permutation of the first n positive integers where n is an odd number. A permutation means that it contains all numbers from 1 to n exactly once in any order. This array perm was transformed into another array named encoded by taking the XOR (exclusive OR) of each pair of adjacent elements in perm. The array encoded has a length of n - 1. For instance, if we take perm = [1,3,2], the resulting encoded array would be [2,1] because 1 XOR 3 = 2 and 3 XOR 2 = 1. Given the encoded array, the task is to find out the original array perm. It is guaranteed that there is one unique solution for this problem.

Intuition

The intuition behind the solution starts by identifying properties of XOR operation. The XOR operation has an important property which is: if a XOR b = c, then it's also true that a XOR c = b and b XOR c = a. This property can be used to retrieve the original permutation from the encoded array.

The first step is to understand that since n is always odd, the XOR of all numbers from 1 to n will give us a single integer because XOR of a number with itself is 0 and the remaining number will be the one without a pair. This number combined with our XOR sequence can be used to deduce the original array.

  1. Compute the XOR of numbers from 1 to n (inclusive), which will be referred to as b.

  2. Since the sequence always starts with the first element of perm (call it perm[0]), we can compute the XOR of the elements at the even positions of encoded. Because encoded[i] = perm[i] XOR perm[i + 1], when we take the XOR of all even encoded[i], we're left with perm[0] XOR perm[2] XOR ... XOR perm[n-1].

  3. Now let's call the result from step 2 as a. Since xor of a includes all even positions of the original permutation, excluding all odd positions, and b includes all positions, a XOR b gives us perm[0], because all even positions except the first position will be canceled out.

  4. Knowing perm[0], we can iterate backwards from the last element of encoded using another property of XOR: perm[i] = encoded[i] XOR perm[i + 1]. This allows us to recover each element of the permutation from perm[n-1] towards perm[0].

By decoding the XOR in this way, we can find out the unique permutation perm that was encoded to give the encoded array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The provided solution follows the intuition and uses the XOR property effectively to decode the original permutation. Here's a step-by-step breakdown of the implementation referencing the python code provided:

  1. First, the length n of the original permutation array perm is identified by adding 1 to the length of the encoded array, since encoded has n-1 elements.

  2. Two variables a and b are initialized to 0. Variable a will hold the result of XOR of all elements at even indices of the encoded array. Variable b will hold the XOR of all integers from 1 to n.

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

  3. A list perm of size n is created and initialized with zeros. The last element of perm is filled with perm[0] which is found out by taking a XOR b. As concluded in the intuition step, a XOR b gives the first element of the original permutation array since b is the XOR of the entire range and a contains XOR of elements at even positions in the original array (which leaves only the first element, since n is odd).

    1perm[-1] = a ^ b

  4. Now that we have the first element, the rest of the permutation elements are retrieved by iterating backwards from the second last element to the first element of perm using the fact that encoded[i] XOR perm[i + 1] yields perm[i].

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

  5. Finally, the perm list is returned, which holds the decoded permutation.

In terms of data structures used, the solution uses a single list perm to hold the decoded permutation. The provided implementation efficiently employs the properties of XOR with simple iteration and list manipulation, avoiding the use of any complex data structures or algorithms. The space complexity is O(n) for storing the result and time complexity O(n) for the decoding, making the algorithm quite efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's illustrate the solution approach with a small example using an encoded array of [3,6,1], which implies n = 4. Here's a step-by-step breakdown:

  1. Determine the length n of the original permutation perm. Since the encoded array has 3 elements, n would be 3 + 1 which is 4.

  2. Initialize two variables a and b to 0. a will store the XOR of encoded elements at even indices (0-based), and b will store the XOR of all integers from 1 to n (inclusive).

  3. Compute the value of a by taking the XOR of encoded elements at even indices:

    1a = encoded[0] XOR encoded[2]
2a = 3 XOR 1
3a = 2

  4. Compute the value of b by taking the XOR of all integers from 1 to n:

    1b = 1 XOR 2 XOR 3 XOR 4
2b = 4

  5. Create a list perm of size n with all zeros and calculate perm[0] using a XOR b because this will cancel out all values except for perm[0]:

    1perm[0] = a XOR b
2perm[0] = 2 XOR 4
3perm[0] = 6

  6. Now with perm[0] known as 6, backtrack to find the other values of original array perm using the property perm[i] = encoded[i] XOR perm[i + 1]:

    1perm[1] = encoded[0] XOR perm[0]
2perm[1] = 3 XOR 6
3perm[1] = 5
4
5perm[2] = encoded[1] XOR perm[1]
6perm[2] = 6 XOR 5
7perm[2] = 3
8
9perm[3] = encoded[2] XOR perm[2]
10perm[3] = 1 XOR 3
11perm[3] = 2

  7. The resulting original permutation array perm is [6,5,3,2].

After following the steps, the perm array obtained is the unique array that was transformed to encoded. The method uses simple XOR operations and leverages the properties of XOR to decode the array efficiently.

Solution Implementation

1class Solution:
2    def decode(self, encoded):
3        # Calculate the size of the original permutation
4        size_of_permutation = len(encoded) + 1
5      
6        # Initialize variables to perform xor operations
7        # `odd_xor` will hold the XOR of encoded elements at odd indices
8        # `total_xor` will hold the XOR of all numbers from 1 to n
9        odd_xor = total_xor = 0
10      
11        # XOR all encoded elements at odd indices (0-based)
12        for index in range(0, size_of_permutation - 1, 2):
13            odd_xor ^= encoded[index]
14      
15        # XOR all numbers from 1 to n to calculate the total_xor
16        for num in range(1, size_of_permutation + 1):
17            total_xor ^= num
18      
19        # Initialize the permutation list with zeros
20        permutation = [0] * size_of_permutation
21      
22        # The last element of the permutation list can be found by XORing odd_xor and total_xor.
23        # This is because the missing XOR'ed number is the first element of the original permutation.
24        permutation[-1] = odd_xor ^ total_xor
25      
26        # Reconstruct the permutation starting from the end,
27        # using the property that encoded[i] = permutation[i] XOR permutation[i+1]
28        for index in range(size_of_permutation - 2, -1, -1):
29            # To find permutation[i], we XOR encoded[i] with permutation[i+1]
30            permutation[index] = encoded[index] ^ permutation[index + 1]
31      
32        # Return the resultant permutation list
33        return permutation
34
1class Solution {
2    public int[] decode(int[] encoded) {
3        // Calculate the size of the original permutation array
4        int n = encoded.length + 1;
5      
6        // Initialize 'xorEven' to perform XOR on even-indexed elements
7        int xorEven = 0;
8      
9        // Initialize 'xorAll' to store the XOR of all numbers from 1 to n
10        int xorAll = 0;
11      
12        // XOR even-indexed elements in the encoded array
13        for (int i = 0; i < n - 1; i += 2) {
14            xorEven ^= encoded[i];
15        }
16      
17        // XOR all numbers from 1 to n to find the XOR of the entire permutation
18        for (int i = 1; i <= n; ++i) {
19            xorAll ^= i;
20        }
21      
22        // Initialize the permutation array to be returned
23        int[] permutation = new int[n];
24      
25        // Find the last element of the permutation by XORing 'xorEven' with 'xorAll', because
26        // the XOR of all elements except the last one has been accounted for in 'xorEven'
27        permutation[n - 1] = xorEven ^ xorAll;
28      
29        // Work backwards to fill in the rest of the permutation array by using the property
30        // that encoded[i] = permutation[i] XOR permutation[i + 1]
31        for (int i = n - 2; i >= 0; --i) {
32            permutation[i] = encoded[i] ^ permutation[i + 1];
33        }
34      
35        // Return the decoded permutation array
36        return permutation;
37    }
38}
39
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> decode(vector<int>& encoded) {
7        // Determine the size of the original permutation
8        int size = encoded.size() + 1;
9      
10        // Initialize two variables to perform XOR operations
11        int oddXor = 0;      // Variable to store the XOR of encoded elements at odd indices
12        int totalXor = 0;    // Variable to store the XOR of all elements in the original permutation
13      
14        // Perform XOR on all odd indexed elements of the encoded array
15        for (int i = 0; i < size - 1; i += 2) {
16            oddXor ^= encoded[i];
17        }
18      
19        // Perform XOR on all numbers from 1 to n (size of the original permutation)
20        for (int i = 1; i <= size; ++i) {
21            totalXor ^= i;
22        }
23      
24        // Create a vector to hold the original permutation
25        vector<int> permutation(size);
26      
27        // Last element of the permutation can be found by XORing oddXor and totalXor
28        permutation[size - 1] = oddXor ^ totalXor;
29      
30        // Reverse-XOR the encoded array starting from the end to compute the original permutation
31        for (int i = size - 2; i >= 0; --i) {
32            permutation[i] = encoded[i] ^ permutation[i + 1];
33        }
34      
35        // Return the original permutation
36        return permutation;
37    }
38};
39
1// Define the decode function, which decodes an encoded array to find the original permutation
2function decode(encoded: number[]): number[] {
3    // Determine the size of the original permutation
4    const size: number = encoded.length + 1;
5  
6    // Initialize variables to perform XOR operations
7    let oddXor: number = 0;      // Variable to store the XOR of encoded elements at odd indices
8    let totalXor: number = 0;    // Variable to store the XOR of all elements in the original permutation
9  
10    // Perform XOR on all odd indexed elements of the encoded array
11    for (let i = 0; i < size - 1; i += 2) {
12        oddXor ^= encoded[i];
13    }
14  
15    // Perform XOR on all numbers from 1 to n (size of the original permutation)
16    for (let i = 1; i <= size; ++i) {
17        totalXor ^= i;
18    }
19  
20    // Create an array to hold the original permutation
21    const permutation: number[] = new Array(size);
22  
23    // The last element of the permutation can be found by XORing oddXor and totalXor
24    permutation[size - 1] = oddXor ^ totalXor;
25  
26    // Reverse-XOR the encoded array starting from the end to compute the original permutation
27    for (let i = size - 2; i >= 0; --i) {
28        permutation[i] = encoded[i] ^ permutation[i + 1];
29    }
30  
31    // Return the original permutation
32    return permutation;
33}
34
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the given algorithm involves iterating over the encoded list and then iterating over a range of numbers from 1 to n to compute the XOR of all elements and the original permutation's elements. Here's the breakdown:

  1. The first for loop runs from 0 to n-1 with a step of 2, resulting in approximately n/2 iterations.
  2. The second for loop runs from 1 to n, inclusive, resulting in n iterations.
  3. The last for loop reverses the encoded array while XORing each element with the next element of the perm list, resulting in n-1 iterations.

Since n, n/2, and n-1 are all linearly proportional to the length of the encoded list, the overall time complexity is O(n).

Space Complexity

The space complexity is determined by:

  1. Variables a and b, which are constant space and thus O(1).
  2. The perm list that stores the result, with a length equal to n, and running n iterations for decoding the permutation.

Since no additional space is used that grows with the input size apart from the perm list, the space complexity is O(n) due to the output data structure.

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

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫