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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decode XORed Permutation

Difficulty: Medium

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 always being odd), return the original array perm.

Key Insights

  • The XOR operation has properties that can help recover values when one of the operands is known.
  • The sum of the first n positive integers can be calculated using the formula n * (n + 1) / 2.
  • The XOR of all elements in perm can be derived from the XOR of the elements in encoded and the first element of perm.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will:

  1. Calculate the XOR of all numbers from 1 to n.
  2. Calculate the XOR of all elements in the encoded array.
  3. Use the relationship between the XOR results to deduce the first element of the perm array.
  4. Iteratively reconstruct the perm array using the XOR values derived from the encoded array.

The algorithm primarily relies on bit manipulation using the XOR operation, which allows us to recover original values from encoded data.

Code Solutions

def decode(encoded):
    n = len(encoded) + 1
    total_xor = 0
    for i in range(1, n + 1):
        total_xor ^= i
    
    encoded_xor = 0
    for num in encoded:
        encoded_xor ^= num

    first_perm = total_xor ^ encoded_xor
    perm = [first_perm]

    for num in encoded:
        next_perm = perm[-1] ^ num
        perm.append(next_perm)

    return perm
← Back to All Questions