Skip to main content
Back to problems
Leetcode
Medium
Arrays
Bit Manipulation
Find The Original Array Of Prefix Xor

Reconstruct an array from its prefix XOR values.

Acceptance 100%
Start Practice
Problem Statement

Problem

You are given an integer array pref where pref[i] represents the XOR of the first i + 1 elements of an original array arr.

Your task is to recover and return the original array arr.

For example, if arr = [a0, a1, a2], then:

  • pref[0] = a0
  • pref[1] = a0 XOR a1
  • pref[2] = a0 XOR a1 XOR a2

Goal

Construct the unique array arr that produces the given prefix XOR array pref.

Input Format

  • A single integer array pref.

Output Format

  • Return an integer array arr such that its prefix XOR values match pref.

Constraints

  • 1 <= pref.length <= $10^{5}$
  • 0 <= pref[i] <= $10^{6}$
  • The original array is guaranteed to exist.

Hints

  • XOR has a self-canceling property: x XOR x = 0.
  • Think about how to derive arr[i] from pref[i] and pref[i - 1].

Input Format

  • One integer array pref representing prefix XOR values.

Output Format

  • Return the recovered original integer array arr.

Constraints

  • 1 <= pref.length <= $10^{5}$
  • 0 <= pref[i] <= $10^{6}$
  • The input is always valid.
Examples
Sample cases returned by the problem API.

Example 1

Input

pref = [5,2,0,3,1]

Output

[5,7,2,3,2]

Explanation

The original array can be recovered as:

  • arr[0] = pref[0] = 5
  • arr[1] = pref[0] XOR pref[1] = 5 XOR 2 = 7
  • arr[2] = pref[1] XOR pref[2] = 2 XOR 0 = 2
  • arr[3] = pref[2] XOR pref[3] = 0 XOR 3 = 3
  • arr[4] = pref[3] XOR pref[4] = 3 XOR 1 = 2

Example 2

Input

pref = [13]

Output

[13]

Explanation

With only one prefix value, the original array contains the same single element.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints
Editorial and discussion links
Concept map and variants
Sign in to unlock
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.
Sign in to track progress