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.

Description Hints 2 Solution Video 13:32

2433. Find The Original Array of Prefix Xor

Medium88.0% acceptance4 companies

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 <= 10⁵
0 <= pref[i] <= 10⁶

Asked at 4 companies

Morgan Stanley NVIDIA

Google Microsoft

Topics

Array Bit Manipulation

Hints open one at a time

Hint 1

Consider the following equation: x ^ a = b. How can you find x?

Hint 2

Notice that arr[i] ^ pref[i-1] = pref[i]. This is the same as the previous equation.

13:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution