Find The Original Array of Prefix Xor

Medium
723.

Find The Original Array of Prefix Xor

Find The Original Array of Prefix Xor is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google, Adobe and Morgan Stanley interviews.

You are given pref, where pref[i] is the XOR of arr[0] … arr[i] for some hidden array arr of the same length.

Reconstruct and return arr. The answer is unique.

Example 1

Input
pref = [5,2,0,3,1]
Output
[5,7,2,3,2]
Explanation
5 = 5, 5 XOR 7 = 2, 2 XOR 2 = 0, 0 XOR 3 = 3, 3 XOR 2 = 1.

Example 2

Input
pref = [13]
Output
[13]

Example 3

Input
pref = [0,0,0]
Output
[0,0,0]

Constraints

  • 1 <= pref.length <= 100000
  • 0 <= pref[i] <= 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[]} pref
 * @return {number[]}
 */
var findArray = function(pref) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find The Original Array of Prefix Xor — Problem & Solution

Find The Original Array of Prefix Xor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find The Original Array of Prefix Xor is a medium coding problem on arrays, bit manipulation and prefix sum, asked in Amazon, Google, Adobe and Morgan Stanley interviews.

Problem statement

You are given pref, where pref[i] is the XOR of arr[0] … arr[i] for some hidden array arr of the same length.

Reconstruct and return arr. The answer is unique.

Example 1

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: 5 = 5, 5 XOR 7 = 2, 2 XOR 2 = 0, 0 XOR 3 = 3, 3 XOR 2 = 1.

Example 2

Input: pref = [13]
Output: [13]

Example 3

Input: pref = [0,0,0]
Output: [0,0,0]

Constraints

  • 1 <= pref.length <= 100000
  • 0 <= pref[i] <= 1000000

Hints for Find The Original Array of Prefix Xor

  1. Hint 1

    pref[i] = pref[i-1] XOR arr[i] by definition.

  2. Hint 2

    XOR is its own inverse, so XOR both sides by pref[i-1].

  3. Hint 3

    That gives arr[i] = pref[i] XOR pref[i-1], with arr[0] = pref[0].

How to solve Find The Original Array of Prefix Xor

The prefix relation inverts directly because XOR undoes itself: knowing consecutive prefixes recovers the element between them.

Approach

  1. Set arr[0] = pref[0].
  2. For each later i, set arr[i] = pref[i] ^ pref[i-1].

Why it works

From pref[i] = pref[i-1] ^ arr[i], XOR-ing both sides by pref[i-1] gives pref[i] ^ pref[i-1] = arr[i], since x ^ x = 0 and x ^ 0 = x. The reconstruction is therefore forced, which is why the answer is unique.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Using subtraction instead of XOR — the relation is not additive.
  • Overwriting pref in place is fine only if you read pref[i-1] before writing pref[i].

Reference solution

Python

from typing import List

def findArray(pref: List[int]) -> List[int]:
    return [pref[0]] + [pref[i] ^ pref[i - 1] for i in range(1, len(pref))]

Java

public static int[] findArray(int[] pref) {
    int n = pref.length;
    int[] out = new int[n];
    out[0] = pref[0];
    for (int i = 1; i < n; i++) out[i] = pref[i] ^ pref[i - 1];
    return out;
}

C++

vector<int> findArray(vector<int>& pref) {
    int n = (int) pref.size();
    vector<int> out(n);
    out[0] = pref[0];
    for (int i = 1; i < n; i++) out[i] = pref[i] ^ pref[i - 1];
    return out;
}

JavaScript

var findArray = function(pref) {
    var out = [pref[0]];
    for (var i = 1; i < pref.length; i++) out.push(pref[i] ^ pref[i - 1]);
    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