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 Array

Difficulty: Easy

Problem Description

Given an encoded integer array encoded of length n - 1, which is derived from a hidden integer array arr such that encoded[i] = arr[i] XOR arr[i + 1], and an integer first that represents the first element of arr, return the original array arr.

Key Insights

  • The encoded array is derived from the original array using the XOR operation.
  • Knowing the first element of the original array allows us to compute the rest of the elements using the property of XOR: arr[i + 1] = encoded[i] XOR arr[i].
  • The solution is linear in time complexity since we only need to iterate through the encoded array once.

Space and Time Complexity

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

Solution

To reconstruct the original array arr, we initialize it with the first element provided. We then iterate through the encoded array, using the XOR operation to derive each subsequent element of arr based on the previous element and the current encoded value. The XOR operation has the property that it can reverse the operation if one of the operands is known.

Code Solutions

def decode(encoded, first):
    n = len(encoded) + 1
    arr = [0] * n
    arr[0] = first
    for i in range(1, n):
        arr[i] = arr[i - 1] ^ encoded[i - 1]
    return arr
← Back to All Questions