Domain 1EasyCORE

Decode XORed Array

The problem requires us to decode an array `arr` from its encoded form `encoded`. The encoding process involves XORing consecutive elements of `arr` to produce the `encoded` array. Specifically, `encoded[i] = arr[i] XOR arr[i + 1]`. We are given the first element of `arr`, and we need to reconstruct the entire array.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1720. Decode XORed Array

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 85.1%


Problem Breakdown

The problem requires us to decode an array arr from its encoded form encoded. The encoding process involves XORing consecutive elements of arr to produce the encoded array. Specifically, encoded[i] = arr[i] XOR arr[i + 1]. We are given the first element of arr, and we need to reconstruct the entire array.

Inputs:

  • encoded: An integer array of length n - 1.
  • first: The first element of the original array arr.

Outputs:

  • The decoded array arr of length n.

Implicit Constraints:

  • The length of arr is one more than the length of encoded.
  • All elements in arr and encoded are non-negative integers.
  • The solution is guaranteed to exist and be unique.

Intuition

A brute-force approach would involve trying all possible combinations for the remaining elements of arr, which is computationally expensive. Instead, we can leverage the properties of XOR to decode the array efficiently.

The key insight is that XOR is its own inverse: a XOR b XOR a = b. This means if we know encoded[i] and arr[i], we can find arr[i + 1] by computing arr[i + 1] = encoded[i] XOR arr[i].

Starting with the given first element, we can iteratively decode each subsequent element using this property.

Approach

  1. Initialize an array arr of length n (where n is one more than the length of encoded).
  2. Set the first element of arr to the given first.
  3. Iterate through the encoded array:
    • For each index i, compute arr[i + 1] = encoded[i] XOR arr[i].
  4. Return the decoded array arr.

This approach leverages the associative and commutative properties of XOR, allowing us to decode the array in a single pass with linear time complexity.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the original array arr. We iterate through the encoded array once.
  • Space Complexity: O(n) for storing the decoded array arr.

Solution

def decode(encoded, first):
    # Initialize the result array with the given first element
    arr = [first]
    
    # Decode each subsequent element using XOR
    for i in range(len(encoded)):
        arr.append(encoded[i] ^ arr[i])
    
    return arr

Edge Cases Handled

  • Single Element Array: If encoded is empty, the function correctly returns an array with just the first element.
  • All Elements Zero: The XOR operation handles cases where all elements are zero without any issues.
  • Maximum Values: The solution works efficiently even when elements are at the upper limit of their range (10^5).