Skip to main content

1734. Decode XORed Permutation

medium

Recover a permutation of [1..n] (n odd) from an encoded array where encoded[i] = perm[i] XOR perm[i+1]. The trick: XOR all of 1..n then XOR every other encoded entry.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 3 <= n < 10^5
  • n is odd.
  • encoded.length == n - 1

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Once you know perm[0], you can reconstruct everything: perm[i+1] = perm[i] XOR encoded[i].

Hint 2

How to find perm[0]? Compute total = perm[0] XOR perm[1] XOR ... XOR perm[n-1] — that's just 1 XOR 2 XOR ... XOR n since perm is a permutation.

Hint 3

Now XOR encoded[1], encoded[3], encoded[5], ... — that's (perm[1] XOR perm[2]) XOR (perm[3] XOR perm[4]) XOR ... — which equals perm[1] XOR perm[2] XOR ... XOR perm[n-1].

Hint 4

perm[0] = total XOR (XOR of odd-indexed encoded entries).

Solution approach

Reveal approach

Recover perm[0] from invariants. Compute total = 1 ^ 2 ^ ... ^ n (the XOR of all values 1 through n, which equals the XOR of the whole permutation regardless of order). Compute odd_xor = encoded[1] ^ encoded[3] ^ encoded[5] ^ ... ^ encoded[n - 2] — these XORs pair up consecutive permutation entries starting from index 1, giving us perm[1] ^ perm[2] ^ ... ^ perm[n - 1]. Then perm[0] = total ^ odd_xor. Once perm[0] is known, fill the rest in one pass: perm[i + 1] = perm[i] ^ encoded[i]. O(n) time, O(n) output space. The whole solution hinges on recognizing that pairing XORs gives you a partial cancellation that, combined with the known full XOR, reveals the missing element.

Complexity

Time
O(n)
Space
O(n) output

Related patterns

  • bit-manipulation
  • xor

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Decode XORed Permutation and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →