Get started

Find The Original Array of Prefix Xor — Medium Problem & Solution

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.

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

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))]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue