Decode XORed Array

Easy
426.

Decode XORed Array

Decode XORed Array is an easy coding problem on arrays and bit manipulation, asked in Amazon and Adobe interviews.

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 <= 39
  • 0 <= encoded[i], first <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} encoded
 * @param {number} first
 * @return {number[]}
 */
var decode = function(encoded, first) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 39
  • 0 <= encoded[i], first <= 1000000

Hints for Decode XORed Array

  1. Hint 1

    XOR is its own inverse: from x ^ y = z and x you recover y = x ^ z.

  2. Hint 2

    So arr[i + 1] = arr[i] XOR encoded[i].

  3. Hint 3

    Start from first and walk forward once.

How to solve Decode XORed Array

XOR is self-inverse, so arr[i+1] = arr[i] ^ encoded[i].

Approach

  1. Start with [first].
  2. Append last ^ encoded[i] for each i.

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 out

Java

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