There is a hidden integer array arr that consists of n non-negative integers.
It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].
You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].
Return the original array arr. It can be proved that the answer exists and is unique.
Example 1:
Input: encoded = [1,2,3], first = 1 Output: [1,0,2,1] Explanation: 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]
Constraints:
2 <= n <= 104encoded.length == n - 10 <= encoded[i] <= 1050 <= first <= 105Problem Overview: You receive an array encoded where each element represents the XOR of two adjacent elements from an unknown array arr. The first element of arr is given as first. Your task is to reconstruct the entire original array.
XOR has a useful property: if a ^ b = c, then a ^ c = b and b ^ c = a. This reversibility makes it possible to recover each next value of the array using the previous value and the encoded entry.
Approach 1: Iterative Decoding using XOR (O(n) time, O(1) space)
This is the standard and most efficient solution. Start by placing first as the first element of the result array. Then iterate through encoded. For each index i, compute the next element using arr[i + 1] = arr[i] ^ encoded[i]. The reason this works is the XOR identity: since encoded[i] = arr[i] ^ arr[i+1], XORing it again with arr[i] cancels out arr[i] and leaves arr[i+1]. The algorithm performs a single pass over the array and updates values sequentially, making it extremely efficient. This approach is the expected solution in interviews when working with bit manipulation and array problems.
Approach 2: Recursive Decoding using XOR (O(n) time, O(n) space)
The same reconstruction logic can be implemented recursively. Start with the base case where the first element is known. A recursive function processes index i and computes the next element using arr[i + 1] = arr[i] ^ encoded[i], then calls itself for the next position. The recursion continues until all elements are reconstructed. While the logic mirrors the iterative solution, recursion adds call stack overhead, leading to O(n) auxiliary space due to recursion depth. This version is mainly useful for practicing recursive reasoning rather than for production efficiency.
Recommended for interviews: The iterative XOR decoding approach is the expected answer. It demonstrates understanding of XOR properties and efficient array traversal with O(n) time and O(1) space. Mentioning the XOR identity explicitly shows strong reasoning with bit manipulation. The recursive variant works but introduces unnecessary stack usage, so it is rarely preferred in interviews.
This approach involves iteratively decoding the encoded array using the properties of the XOR operation. Since XOR is its own inverse, we can retrieve the next element of the arr by using the relation: arr[i + 1] = encoded[i] XOR arr[i]. Starting with first as the first element of the arr, we can decode the entire array.
In this C implementation, we initialize an array arr to store the decoded values. The first element is set as first. We then iterate through the encoded array using the relation arr[i + 1] = arr[i] ^ encoded[i] to fill up the arr array.
Time Complexity: O(n), where n is the length of the original array.
Space Complexity: O(n), for storing the decoded array.
This approach uses recursion to decode the array. The XOR properties allow us to recursively calculate the original elements by passing the current index and constructing the array one element at a time.
The C solution defines a recursive function decodeRecursive which decodes elements using XOR and recursion. It constructs the array starting from the second element, recursing till all elements are decoded.
Time Complexity: O(n)
Space Complexity: O(n) for stack space.
Based on the problem description, we have:
$
encoded[i] = arr[i] \oplus arr[i + 1]
If we XOR both sides of the equation with arr[i], we get:
arr[i] \oplus arr[i] \oplus arr[i + 1] = arr[i] \oplus encoded[i]
Which simplifies to:
arr[i + 1] = arr[i] \oplus encoded[i]
Following the derivation above, we can start with first and sequentially calculate every element of the array arr.
The time complexity is O(n), and the space complexity is O(n), where n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Decoding using XOR | Time Complexity: O(n), where n is the length of the original array. |
| Recursive Decoding using XOR | Time Complexity: O(n) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Decoding using XOR | O(n) | O(1) | Best general solution. Minimal memory usage and single pass reconstruction. |
| Recursive Decoding using XOR | O(n) | O(n) | Useful for understanding recursion patterns but less efficient due to stack space. |
1720. Decode XORed Array (Leetcode Easy) • Programming Live with Larry • 3,880 views views
Watch 9 more video solutions →Practice Decode XORed Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor