Watch 10 video solutions for Decode XORed Array, a easy level problem involving Array, Bit Manipulation. This walkthrough by Programming Live with Larry has 3,880 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |