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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →