#1720

Easy

LeetCode Problem Workspace

Decode XORed Array

Recover the original integer array from its XOR-encoded version using direct bitwise manipulation and sequential reconstruction logic.

array bit manipulation

Problem Statement

You are given an integer array encoded of length n - 1, which represents the XOR encoding of a hidden array arr of length n. Specifically, encoded[i] = arr[i] XOR arr[i + 1]. Additionally, you are provided an integer first, which is the first element of arr. Your task is to reconstruct the original array arr.

Return the original array arr that generated encoded using the XOR relationship. For example, if first = 1 and encoded = [1,2,3], then arr = [1,0,2,1]. Ensure your solution handles arrays up to length 104 and values up to 105 efficiently.

Examples

Example 1

Input: encoded = [1,2,3], first = 1

Output: [1,0,2,1]

If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2

Input: encoded = [6,2,7,3], first = 4

Output: [4,2,0,7,4]

Example details omitted.

Constraints

2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105

Solution Approach

Iterative Reconstruction Using XOR

Start with arr[0] = first. For each index i from 0 to encoded.length - 1, compute arr[i + 1] = encoded[i] XOR arr[i]. This sequential approach directly leverages the XOR encoding pattern and guarantees correct reconstruction in a single pass.

Avoid Extra Data Structures

No additional hash maps or lists are necessary. Maintain a single array arr for output. This minimizes space usage and focuses on the bit manipulation property of XOR to compute the next element immediately.

Verify With Example Patterns

Check small examples to ensure correctness: for encoded = [1,2,3] and first = 1, the reconstruction produces [1,0,2,1]. Recognizing the XOR pattern prevents off-by-one mistakes and incorrect indexing, which are common pitfalls in array reconstruction problems.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each encoded element is processed exactly once. Space complexity is O(n) for storing the reconstructed arr. No additional overhead is required beyond the output array.

What Interviewers Usually Probe

Watch for off-by-one errors in indexing while reconstructing arr using XOR.
Expect candidates to apply arr[i+1] = encoded[i] XOR arr[i] directly without extra data structures.
Check understanding of bit manipulation patterns and sequential array reconstruction.

Common Pitfalls or Variants

Common pitfalls

Incorrectly starting reconstruction from the wrong index, leading to all subsequent values being wrong.
Confusing XOR with addition or other bitwise operations, resulting in wrong output.
Allocating extra arrays or using unnecessary loops that increase time or space complexity.

Follow-up variants

The array may contain larger integers up to 10^6 to test handling of bigger numbers with XOR.
Provide multiple first elements or partial arr segments and ask for reconstruction of the remaining array.
Encode arr with a different bitwise operator, such as AND or OR, to test understanding of operator-specific reconstruction.

FAQ

What is the simplest method to decode a XORed array?

Start with the given first element and iteratively compute arr[i+1] = encoded[i] XOR arr[i]. This method ensures accurate reconstruction.

Does the solution require extra memory beyond the output array?

No, only the array to store the reconstructed arr is necessary; no additional data structures are required.

Can this approach handle the maximum constraints of n = 104?

Yes, the O(n) time and O(n) space approach scales efficiently even for arrays of length 104.

What are common mistakes when solving Decode XORed Array?

Off-by-one indexing, confusing XOR with addition, and using unnecessary loops or extra arrays are frequent errors.

Is there a shortcut to verify if the decoded array is correct?

Recompute encoded by XORing consecutive elements of the reconstructed arr; it should match the original encoded array.

terminal

Solution

Solution 1: Bit Manipulation

Based on the problem description, we have:

1

2

3

4

5

6

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        ans = [first]
        for x in encoded:
            ans.append(ans[-1] ^ x)
        return ans

Continue Practicing

#1723 find minimum time to finish all jobs #1707 maximum xor with an element from array #1734 decode xored permutation