Skip to main content
Talentd

Find The Original Array of Prefix Xor - Solution & Explanation

MediumArrayBit Manipulation16 min readAsked at: Microsoft, Morgan Stanley, NVIDIA +1
Practice this problem

Problem Statement

You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

  • pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

 

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

 

Constraints:

  • 1 <= pref.length <= 105
  • 0 <= pref[i] <= 106

Approach Overview

Problem Overview: You are given an array pref where pref[i] represents the XOR of all elements from index 0 to i in the original array. Your task is to reconstruct the original array that produced this prefix XOR sequence.

The key observation comes from XOR properties. If pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i], then XORing two consecutive prefix values cancels the common part. This allows you to isolate each element of the original array.

Approach 1: Iterative Approach (O(n) time, O(1) space)

Create the result array and compute elements sequentially. The first element is straightforward: arr[0] = pref[0]. For every index i > 0, the previous prefix contains arr[0] ^ ... ^ arr[i-1]. XORing pref[i] with pref[i-1] cancels that shared portion and leaves only arr[i]. Iterate through the array once and apply this operation to recover each value.

This approach works because XOR has two useful properties: a ^ a = 0 and a ^ 0 = a. When you compute pref[i] ^ pref[i-1], all earlier elements cancel out. The algorithm requires only a single pass through the array and constant extra memory.

Approach 2: Prefix XOR Direct Computation (O(n) time, O(1) space)

This method uses the same mathematical relationship but frames it directly from the prefix XOR definition. The original array satisfies: arr[i] = pref[i] ^ pref[i-1]. Initialize the first element from the prefix array, then compute each subsequent element using this formula.

Instead of maintaining additional structures, you simply read the current and previous prefix values. The algorithm performs one XOR operation per element, making it extremely efficient. This approach is common in problems involving bit manipulation and prefix transformations on an array.

Recommended for interviews: The direct prefix XOR computation is the expected solution. Interviewers want to see that you recognize how prefix XOR works and apply the identity pref[i] ^ pref[i-1]. Mentioning the XOR cancellation property demonstrates a solid understanding of bit manipulation. A brute-force reconstruction would be unnecessary here, while the O(n) prefix-based approach shows you understand both the math and the implementation.

Approach 1: Iterative Approach

This approach involves iterating through the prefix XOR array and using the properties of XOR to deduce the original array. Starting from the first element, which is the same as in the original array, subsequent elements can be found using the formula:

arr[i] = pref[i] ^ pref[i-1]

since pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] and pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1].

This C program first stores the first element in the pref array into the arr array since they are the same. For subsequent elements, it uses the XOR operation with the previous prefix value to deduce the original numbers. The use of a simple loop makes the implementation straightforward.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Prefix XOR Direct Computation

This approach calculates each element of the original array directly by using the property of XOR that makes it its own inverse. By understanding that the difference between consecutive prefix values gives the desired element, this method is implemented in a direct computational manner.

This C solution reflects the direct calculation of the original array using XOR directly on the prefix elements. Using principles similar to other approaches, this code shows how directly the computation can be managed given the XOR properties.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Bit Manipulation

According to the problem statement, we have equation one:

$ pref[i]=arr[0] \oplus arr[1] \oplus cdots \oplus arr[i]

So, we also have equation two:

pref[i-1]=arr[0] \oplus arr[1] \oplus cdots \oplus arr[i-1]

We perform a bitwise XOR operation on equations one and two, and get:

pref[i] \oplus pref[i-1]=arr[i]

That is, each item in the answer array is obtained by performing a bitwise XOR operation on the adjacent two items in the prefix XOR array.

The time complexity is O(n), where n is the length of the prefix XOR array. Ignoring the space consumption of the answer, the space complexity is O(1)$.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n)
Space Complexity: O(n)

Prefix XOR Direct Computation

Time Complexity: O(n)
Space Complexity: O(n)

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative ApproachO(n)O(1)General case when reconstructing the array sequentially from prefix values
Prefix XOR Direct ComputationO(n)O(1)Best approach when leveraging XOR cancellation between consecutive prefix values

Video Solution

Find The Original Array of Prefix Xor | XOR Properties | Microsoft | Leetcode - 2433 • codestorywithMIK • 10,632 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find The Original Array of Prefix Xor easy or hard?
The problem is rated Medium on LeetCode but is conceptually straightforward once you recognize the XOR prefix property. Understanding how XOR cancels identical values makes the reconstruction step immediate.
Find The Original Array of Prefix Xor Python/Java solution
In Python or Java, iterate through the prefix array and compute arr[i] = pref[i] ^ pref[i-1] for i > 0, with arr[0] = pref[0]. This implementation takes O(n) time and constant extra space and works identically across languages.
How to solve Find The Original Array of Prefix Xor in O(n)?
Start with arr[0] = pref[0]. For every index i greater than 0, compute arr[i] = pref[i] ^ pref[i-1]. XORing consecutive prefix values removes the common prefix portion and isolates the current element, allowing reconstruction in a single linear scan.
What is the best approach for Find The Original Array of Prefix Xor?
The best approach uses the XOR cancellation property. If pref[i] represents the XOR from index 0 to i, then the original value can be recovered with arr[i] = pref[i] ^ pref[i-1]. This produces the array in O(n) time and O(1) extra space with a single pass.
Is Find The Original Array of Prefix Xor asked at Google/Amazon/Meta?
Problems involving prefix XOR and bit manipulation appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the concept of reversing prefix operations and applying XOR properties is a common interview pattern.
What data structure is used in Find The Original Array of Prefix Xor?
The solution primarily works with arrays and uses bit manipulation through XOR operations. No additional data structures such as hash maps or stacks are required because the prefix relationship directly reveals each element.
What is the time complexity of Find The Original Array of Prefix Xor?
The optimal solution runs in O(n) time because each element is computed exactly once. Only one XOR operation per index is required. Space complexity is O(1) excluding the output array since no additional data structures are needed.

Ready to solve this problem?

Practice Find The Original Array of Prefix Xor with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Triplets That Can Form Two Arrays of Equal XOR

Next

Decode XORed Array