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.

Description Hints 2 Solution Video 4:47

1720. Decode XORed Array

Easy87.3% acceptance1 company

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 <= 10⁴
encoded.length == n - 1
0 <= encoded[i] <= 10⁵
0 <= first <= 10⁵

Asked at 1 company

Google

Topics

Array Bit Manipulation

Hints open one at a time

Hint 1

Since that encoded[i] = arr[i] XOR arr[i+1], then arr[i+1] = encoded[i] XOR arr[i].

Hint 2

Iterate on i from beginning to end, and set arr[i+1] = encoded[i] XOR arr[i].

4:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution