Decode XORed Array solution and explanation
Google
9 more videos on this problem
1720. Decode XORed Array (Leetcode Easy)Programming Live with Larry · 4:47 · 3K views
1720. Decode XORed Array LEETCODE problem , Explanation and code /C++Coding with U · 6:22 · 3K views
LeetCode - Decode XORed Array in PythonKnowledge Mavens · 10:06 · 1K views
LEETCODE SOLUTION 1720 | Decode XoRed Array | Leetcode for BEGINNERS | EASY | Javascript | CODINGCodingForBeginners · 8:51 · 1K views
LeetCode 1720 | Decode XORed Array | Array | JavaSleepy Cracker · 2:24 · 963 views
Solving LeetCode problem 1720 in APL (Decode XORed Array)Rodrigo's APL Corner · 13:37 · 324 views
1720. Decode XORed Array || LeetCode 1720 || Java Problem Easy SolutionTech Demand · 3:46 · 263 views
LeetCode - 1720. Decode XORed Array | Bit Manipulation | JavaOrkhan Gasanov · 3:46 · 181 views
1720. Decode XORed Array(Easy)CS++; · 5:16 · 163 views
Decode XORed Array | Leetcode 1720 | Approach + Code with explanation.Pirai's Academy · 4:28 · 133 views
The problem
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 <= 105
Approach overview
Problem 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 1: Iterative Decoding using XOR
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.
def decode(encoded, first):
arr = [first]
for e in encoded:
arr.append(arr[-1] ^ e)
return arrclass Solution {
public int[] decode(int[] encoded, int first) {
int n = encoded.length + 1;
int[] arr = new int[n];
arr[0] = first;
for (int i = 0; i < encoded.length; i++) {
arr[i + 1] = arr[i] ^ encoded[i];
}
return arr;
}
}#include <vector>
std::vector<int> decode(const std::vector<int>& encoded, int first) {
int n = encoded.size() + 1;
std::vector<int> arr(n);
arr[0] = first;
for (size_t i = 0; i < encoded.size(); ++i) {
arr[i + 1] = arr[i] ^ encoded[i];
}
return arr;
}function decode(encoded, first) {
let arr = [first];
for (let i = 0; i < encoded.length; i++) {
arr.push(arr[i] ^ encoded[i]);
}
return arr;
}#include <stdio.h>
#include <stdlib.h>
int* decode(int* encoded, int encodedSize, int first, int* returnSize){
int n = encodedSize + 1;
int* arr = (int*) malloc(n * sizeof(int));
arr[0] = first;
for (int i = 0; i < encodedSize; i++) {
arr[i + 1] = arr[i] ^ encoded[i];
}
*returnSize = n;
return arr;
}public class Solution {
public int[] Decode(int[] encoded, int first) {
int n = encoded.Length + 1;
int[] arr = new int[n];
arr[0] = first;
for (int i = 0; i < encoded.Length; i++) {
arr[i + 1] = arr[i] ^ encoded[i];
}
return arr;
}
}In this Python implementation, we start with a list arr initialized with first. We then iteratively append arr[-1] ^ e to the list for each element e in the encoded array.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Recursive Decoding using XOR
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.
def decode(encoded, first):
arr = [first]
def decode_recursive(index):
if index == len(encoded):
return
arr.append(arr[-1] ^ encoded[index])
decode_recursive(index + 1)
decode_recursive(0)
return arrclass Solution {
private void decodeRecursive(int[] encoded, int[] arr, int index) {
if (index == encoded.length) return;
arr[index + 1] = arr[index] ^ encoded[index];
decodeRecursive(encoded, arr, index + 1);
}
public int[] decode(int[] encoded, int first) {
int n = encoded.length + 1;
int[] arr = new int[n];
arr[0] = first;
decodeRecursive(encoded, arr, 0);
return arr;
}
}#include <vector>
void decodeRecursive(const std::vector<int>& encoded, std::vector<int>& arr, int index) {
if(index == encoded.size()) return;
arr[index + 1] = arr[index] ^ encoded[index];
decodeRecursive(encoded, arr, index + 1);
}
std::vector<int> decode(const std::vector<int>& encoded, int first) {
int n = encoded.size() + 1;
std::vector<int> arr(n);
arr[0] = first;
decodeRecursive(encoded, arr, 0);
return arr;
}function decode(encoded, first) {
let arr = [first];
(function decodeRecursive(index) {
if (index === encoded.length) return;
arr.push(arr[arr.length - 1] ^ encoded[index]);
decodeRecursive(index + 1);
})(0);
return arr;
}#include <stdio.h>
#include <stdlib.h>
void decodeRecursive(int* encoded, int* arr, int index, int encodedSize) {
if (index == encodedSize) return;
arr[index + 1] = arr[index] ^ encoded[index];
decodeRecursive(encoded, arr, index + 1, encodedSize);
}
int* decode(int* encoded, int encodedSize, int first, int* returnSize) {
int n = encodedSize + 1;
int* arr = (int*) malloc(n * sizeof(int));
arr[0] = first;
decodeRecursive(encoded, arr, 0, encodedSize);
*returnSize = n;
return arr;
}public class Solution {
private void DecodeRecursive(int[] encoded, int[] arr, int index) {
if (index == encoded.Length) return;
arr[index + 1] = arr[index] ^ encoded[index];
DecodeRecursive(encoded, arr, index + 1);
}
public int[] Decode(int[] encoded, int first) {
int n = encoded.Length + 1;
int[] arr = new int[n];
arr[0] = first;
DecodeRecursive(encoded, arr, 0);
return arr;
}
}This Python solution uses an inner recursive function, decode_recursive, which appends new elements to the array by XORing based on the previous value until the entire array is decoded.
Time Complexity: O(n)
Space Complexity: O(n) for stack space.
Approach 3: Bit Manipulation
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.
function decode(encoded: number[], first: number): number[] {
const ans: number[] = [first];
for (const x of encoded) {
ans.push(ans.at(-1)! ^ x);
}
return ans;
}func decode(encoded []int, first int) []int {
ans := []int{first}
for i, x := range encoded {
ans = append(ans, ans[i]^x)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Decoding using XOR | Time Complexity: O(n) |
| Recursive Decoding using XOR | Time Complexity: O(n) |
| Bit Manipulation | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Decode XORed Array easy or hard?
Decode XORed Array is classified as an Easy problem. Once you recognize the reversible property of XOR (a ^ b ^ a = b), reconstructing the array becomes a straightforward linear scan.
Decode XORed Array Python/Java solution
Python, Java, C++, C#, and JavaScript implementations all follow the same logic: initialize the first value and iteratively compute arr[i + 1] = arr[i] ^ encoded[i]. The language differences are minimal because XOR is a built-in operator in most languages.
How to solve Decode XORed Array in O(n)?
Initialize the result array with the provided first value. Iterate through the encoded array and compute each next element using arr[i + 1] = arr[i] ^ encoded[i]. Because XOR cancels identical operands, this directly recovers the next value. The algorithm completes in linear time.
What is the best approach for Decode XORed Array?
The best approach is iterative XOR decoding. Start with the given first element and reconstruct each next value using arr[i + 1] = arr[i] ^ encoded[i]. This runs in O(n) time with O(1) extra space and requires only a single pass through the encoded array.
Is Decode XORed Array asked at Google/Amazon/Meta?
This problem is representative of bit manipulation questions commonly asked in technical interviews. Variations involving XOR properties frequently appear at companies like Amazon, Google, and Meta to test understanding of bitwise operations and array reconstruction.
What data structure is used in Decode XORed Array?
The solution primarily uses arrays and bitwise XOR operations. No advanced data structures are required because each element can be reconstructed directly from the previous value and the encoded array.
What is the time complexity of Decode XORed Array?
The optimal solution runs in O(n) time where n is the length of the encoded array. Each element is processed exactly once to compute the next value in the original array.