Skip to main content
Talentd

Decode XORed Array - Solution & Explanation

EasyArrayBit Manipulation13 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the original array.
Space Complexity: O(n), for storing the decoded array.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) for stack space.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Decoding using XOR

Time Complexity: O(n), where n is the length of the original array.
Space Complexity: O(n), for storing the decoded array.

Recursive Decoding using XOR

Time Complexity: O(n)
Space Complexity: O(n) for stack space.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Decoding using XORO(n)O(1)Best general solution. Minimal memory usage and single pass reconstruction.
Recursive Decoding using XORO(n)O(n)Useful for understanding recursion patterns but less efficient due to stack space.

Video Solution

1720. Decode XORed Array (Leetcode Easy) • Programming Live with Larry • 3,883 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Decode XORed Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find The Original Array of Prefix Xor