Decode XORed Array — Solution in Python, Java & C++
Decode XORed Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Decode XORed Array is an easy coding problem on arrays and bit manipulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Bit Manipulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An array arr of n non-negative integers was encoded into an array encoded of length n - 1 with encoded[i] = arr[i] XOR arr[i + 1].
Given encoded and the value first — that is, arr[0] — recover and return the original array arr.
Example 1
Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Example 2
Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]
Example 3
Input: encoded = [5], first = 3
Output: [3,6]
Constraints
1 <= encoded.length <= 390 <= encoded[i], first <= 1000000
Hints for Decode XORed Array
Hint 1
XOR is its own inverse: from
x ^ y = zandxyou recovery = x ^ z.Hint 2
So
arr[i + 1] = arr[i] XOR encoded[i].Hint 3
Start from
firstand walk forward once.
How to solve Decode XORed Array
XOR is self-inverse, so arr[i+1] = arr[i] ^ encoded[i].
Approach
- Start with
[first]. - Append
last ^ encoded[i]for eachi.
Why it works
From arr[i] ^ arr[i+1] = encoded[i], XORing both sides with arr[i] isolates arr[i+1].
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The output has one more element than
encoded.
Reference solution
Python
def decode(encoded, first: int):
out = [first]
for x in encoded:
out.append(out[-1] ^ x)
return outJava
public static int[] decode(int[] encoded, int first) {
int[] out = new int[encoded.length + 1];
out[0] = first;
for (int i = 0; i < encoded.length; i++) out[i + 1] = out[i] ^ encoded[i];
return out;
}C++
vector<int> decode(vector<int>& encoded, int first) {
vector<int> out(encoded.size() + 1);
out[0] = first;
for (size_t i = 0; i < encoded.size(); i++) out[i + 1] = out[i] ^ encoded[i];
return out;
}JavaScript
var decode = function(encoded, first) {
const out = [first];
for (let i = 0; i < encoded.length; i++) out.push(out[i] ^ encoded[i]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation