We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decode XORed Permutation

Number: 1835

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array encoded of length n-1 where encoded[i] = perm[i] XOR perm[i+1] and perm is a permutation of the first n positive integers (with n being odd), recover the original array perm.

Key Insights

  • The XOR operation is both associative and commutative.
  • The total XOR of all numbers from 1 to n can be computed.
  • XORing selective elements of the encoded array can help isolate the first element of perm due to cancellation properties.
  • Once the first element is known, the rest of the permutation can be derived by sequentially XORing with the encoded values.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n) (to store the result array)

Solution

The approach is to first compute the XOR of all numbers from 1 to n. Then, observe that XORing every second element of the encoded array (starting from index 1) gives the XOR of the elements of perm except the first one. By XORing this result with the total XOR, we can determine the first element of perm. Following that, we iteratively recover each subsequent element by XORing the previous element with the corresponding element from encoded. The key data structures used are simple integers and arrays, and the algorithm leverages the properties of XOR to efficiently decode the permutation in one pass.

Code Solutions

# Python solution
def decode(encoded):
    n = len(encoded) + 1
    total_xor = 0
    # Compute XOR of all numbers from 1 to n
    for i in range(1, n + 1):
        total_xor ^= i
    odd_xor = 0
    # XOR encoded elements at odd indices (1-indexed even indices)
    for i in range(1, len(encoded), 2):
        odd_xor ^= encoded[i]
    # The first element of perm
    first = total_xor ^ odd_xor
    perm = [first]
    # Recover the entire permutation
    for num in encoded:
        perm.append(perm[-1] ^ num)
    return perm

# Example usage:
# print(decode([6,5,4,6]))  # Expected output: [2,4,1,5,3]
← Back to All Questions