LeetCode 1734 - Decode XORed Permutation

The problem gives us an array called encoded, which was generated from an unknown permutation array perm. A permutation of the first n positive integers means the array contains every integer from 1 to n exactly once. For example: - [1,2,3] is a valid permutation of 1..

leetcodemediumarraybit-manipulation

LeetCode Problem 1734

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives us an array called encoded, which was generated from an unknown permutation array perm.

A permutation of the first n positive integers means the array contains every integer from 1 to n exactly once. For example:

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

The encoding rule is:

encoded[i] = perm[i] XOR perm[i + 1]

where XOR is the bitwise exclusive OR operation.

We are given only the encoded array and must reconstruct the original perm array.

The important detail is that n is always odd. Since encoded.length == n - 1, we can compute:

n = encoded.length + 1

The constraints allow n up to 10^5, which immediately tells us that brute force permutation generation is infeasible. Any factorial-time approach would be astronomically slow.

The problem also guarantees that the answer exists and is unique. That means we do not need to worry about ambiguous reconstructions or invalid inputs.

A few important observations:

  • XOR has useful cancellation properties:

  • a XOR a = 0

  • a XOR 0 = a

  • XOR is associative and commutative

  • Because perm is a permutation of 1..n, the XOR of all elements in perm is simply:

1 XOR 2 XOR 3 XOR ... XOR n

Potential pitfalls for a naive implementation include:

  • Forgetting that n is odd, which is essential for the mathematical trick
  • Misunderstanding which indices in encoded should be XORed together
  • Incorrectly reconstructing the permutation after discovering the first element
  • Using factorial brute force approaches that cannot scale to 10^5

Approaches

Brute Force Approach

The most direct idea is to try every possible permutation of the numbers 1..n.

For each permutation:

  1. Compute the encoded representation.
  2. Compare it against the given encoded array.
  3. Return the permutation if it matches.

This works because the problem guarantees a unique valid answer. Eventually, we would find the correct permutation.

However, this approach is completely impractical.

There are n! possible permutations. Even for relatively small n, this becomes enormous:

10! = 3,628,800
15! = 1,307,674,368,000

Since n can be as large as 100000, brute force is impossible.

Optimal Approach

The key insight comes from XOR properties and the fact that perm is a permutation of 1..n.

Suppose:

perm = [p0, p1, p2, p3, p4]
encoded = [p0^p1, p1^p2, p2^p3, p3^p4]

If we XOR all elements of encoded at odd indices:

encoded[1] XOR encoded[3]
=
(p1^p2) XOR (p3^p4)

Notice that this gives us all elements of perm except p0.

Now compute:

total = 1 XOR 2 XOR ... XOR n

Since:

total = p0 XOR p1 XOR p2 XOR p3 XOR p4

we can recover:

p0 = total XOR (p1 XOR p2 XOR p3 XOR p4)

Once we know the first element, the rest can be reconstructed sequentially:

encoded[i] = perm[i] XOR perm[i+1]

therefore:

perm[i+1] = perm[i] XOR encoded[i]

This gives a linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n) Tries every permutation
Optimal O(n) O(1) extra space Uses XOR properties to reconstruct directly

Algorithm Walkthrough

  1. Compute n as len(encoded) + 1.

Since the encoded array has length n - 1, we can recover the size of the original permutation immediately. 2. Compute the XOR of all integers from 1 to n.

This value represents the XOR of every element in perm, because perm is a permutation of exactly those numbers. 3. Compute the XOR of encoded elements at odd indices.

Specifically, XOR:

encoded[1], encoded[3], encoded[5], ...

Each of these values expands into XORs of adjacent permutation elements.

Because of cancellation properties, this produces:

perm[1] XOR perm[2] XOR ... XOR perm[n-1]
  1. Recover the first element of perm.

Since:

total_xor = perm[0] XOR perm[1] XOR ... XOR perm[n-1]

and we already computed:

perm[1] XOR perm[2] XOR ... XOR perm[n-1]

we can isolate:

perm[0] = total_xor XOR odd_encoded_xor
  1. Reconstruct the remaining elements.

Using:

encoded[i] = perm[i] XOR perm[i+1]

rearrange to get:

perm[i+1] = perm[i] XOR encoded[i]

Iterate through encoded and build the permutation one element at a time.

Why it works

The algorithm works because XOR allows cancellation of duplicate values. XORing the odd-indexed encoded values gives all permutation elements except the first one. Since we also know the XOR of the complete permutation from 1..n, we can isolate the first element exactly. Once the first element is known, every subsequent element is uniquely determined by the encoding relationship.

Python Solution

from typing import List

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1

        # XOR of all numbers from 1 to n
        total_xor = 0
        for num in range(1, n + 1):
            total_xor ^= num

        # XOR of encoded elements at odd indices
        odd_xor = 0
        for i in range(1, len(encoded), 2):
            odd_xor ^= encoded[i]

        # Recover first element of perm
        first = total_xor ^ odd_xor

        # Reconstruct permutation
        perm = [first]

        for value in encoded:
            perm.append(perm[-1] ^ value)

        return perm

The implementation begins by determining the size of the permutation. Since encoded has length n - 1, adding one gives the original permutation length.

Next, the code computes the XOR of all integers from 1 to n. Because the permutation contains exactly these values, this XOR represents the XOR of every permutation element.

The loop over odd indices in encoded extracts the XOR of all permutation elements except the first. This is the mathematical trick that makes the problem solvable in linear time.

After recovering the first element, the remainder of the permutation is reconstructed sequentially. Every encoded value stores the XOR of adjacent permutation elements, so knowing one element immediately determines the next.

The reconstruction loop appends each new value to the result list until the full permutation is restored.

Go Solution

func decode(encoded []int) []int {
	n := len(encoded) + 1

	// XOR of all numbers from 1 to n
	totalXor := 0
	for i := 1; i <= n; i++ {
		totalXor ^= i
	}

	// XOR of encoded elements at odd indices
	oddXor := 0
	for i := 1; i < len(encoded); i += 2 {
		oddXor ^= encoded[i]
	}

	// Recover first element
	first := totalXor ^ oddXor

	// Reconstruct permutation
	perm := make([]int, n)
	perm[0] = first

	for i := 0; i < len(encoded); i++ {
		perm[i+1] = perm[i] ^ encoded[i]
	}

	return perm
}

The Go implementation follows the exact same logic as the Python solution. The main difference is explicit slice allocation with make, which avoids repeated dynamic resizing during reconstruction.

Go integers are sufficient for this problem because all values remain well within standard integer limits. Since XOR is a bitwise operation, there are no overflow concerns in practice for the given constraints.

Worked Examples

Example 1

Input: encoded = [3,1]

First compute:

n = 3

The permutation must contain:

[1,2,3]

Step 1: XOR all numbers from 1 to n

Number Running XOR
1 1
2 1 ^ 2 = 3
3 3 ^ 3 = 0

So:

total_xor = 0

Step 2: XOR odd-indexed encoded values

Odd indices:

encoded[1] = 1

So:

odd_xor = 1

Step 3: Recover first element

first = total_xor ^ odd_xor
       = 0 ^ 1
       = 1

Now:

perm = [1]

Step 4: Reconstruct remaining values

Encoded Value Calculation New Element
3 1 ^ 3 2
1 2 ^ 1 3

Final result:

[1,2,3]

Example 2

Input: encoded = [6,5,4,6]

Step 1: Compute n

n = 5

Step 2: XOR all numbers from 1 to 5

Number Running XOR
1 1
2 3
3 0
4 4
5 1

So:

total_xor = 1

Step 3: XOR odd-indexed encoded values

Odd indices:

encoded[1] = 5
encoded[3] = 6

Compute:

odd_xor = 5 ^ 6 = 3

Step 4: Recover first element

first = 1 ^ 3 = 2

Now:

perm = [2]

Step 5: Reconstruct the permutation

Encoded Value Calculation New Element
6 2 ^ 6 4
5 4 ^ 5 1
4 1 ^ 4 5
6 5 ^ 6 3

Final result:

[2,4,1,5,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each loop processes the array once
Space O(1) extra space Only a few variables are used besides the output array

The algorithm performs several linear passes over the input:

  • One pass to XOR numbers from 1 to n
  • One pass over odd indices
  • One pass to reconstruct the permutation

Since all passes are linear and independent, the total time complexity remains O(n).

The algorithm uses constant auxiliary memory. The output array itself is required and does not count toward extra space complexity.

Test Cases

from typing import List

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1

        total_xor = 0
        for num in range(1, n + 1):
            total_xor ^= num

        odd_xor = 0
        for i in range(1, len(encoded), 2):
            odd_xor ^= encoded[i]

        first = total_xor ^ odd_xor

        perm = [first]

        for value in encoded:
            perm.append(perm[-1] ^ value)

        return perm

solution = Solution()

assert solution.decode([3, 1]) == [1, 2, 3]  # Example 1
assert solution.decode([6, 5, 4, 6]) == [2, 4, 1, 5, 3]  # Example 2

assert solution.decode([1, 2]) == [2, 3, 1]  # Smallest valid n
assert solution.decode([2, 1]) == [3, 1, 2]  # Different permutation order

assert solution.decode([5, 2, 1, 6]) == [3, 6, 4, 5, 3 ^ 6 ^ 4 ^ 5 ^ 5 ^ 2 ^ 1 ^ 6]  # Stress XOR transitions

# Larger permutation test
encoded = [7, 3, 2, 6, 4, 5]
result = solution.decode(encoded)

# Validate permutation properties
n = len(encoded) + 1
assert sorted(result) == list(range(1, n + 1))  # Must contain all values 1..n

# Validate encoding reconstruction
for i in range(len(encoded)):
    assert (result[i] ^ result[i + 1]) == encoded[i]
Test Why
[3,1] Validates the simplest example
[6,5,4,6] Tests a larger permutation
[1,2] Smallest allowed odd-sized permutation
[2,1] Ensures reconstruction works for non-sorted permutations
Complex XOR transitions Verifies repeated XOR chaining
Larger permutation validation Confirms permutation correctness and encoding consistency

Edge Cases

Smallest Valid Input

The smallest possible permutation size is n = 3, because n must be odd and at least 3.

This is important because algorithms that incorrectly assume larger arrays may fail on boundary conditions. The implementation handles this naturally because all loops still execute correctly for arrays of length 2.

Non-Sorted Permutations

The permutation is not guaranteed to be sorted. A buggy solution might accidentally assume values increase or follow a predictable pattern.

For example:

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

The implementation never relies on ordering. It reconstructs values solely using XOR relationships, so arbitrary permutations work correctly.

Large Inputs Near Constraint Limits

The input size can approach 100000, making inefficient solutions impossible.

A brute force or backtracking solution would time out immediately. The implemented algorithm uses only linear passes over the data, so it scales efficiently even for maximum-size inputs.

XOR Cancellation Pitfalls

A common mistake is XORing the wrong subset of encoded indices.

Only odd indices are used because:

encoded[1] = perm[1] ^ perm[2]
encoded[3] = perm[3] ^ perm[4]

This pattern excludes perm[0], allowing it to be isolated later. Using even indices would not produce the correct cancellation behavior.