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 <= 1050 <= pref[i] <= 106Problem 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.
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.
Time Complexity: O(n)
Space Complexity: O(n)
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.
Time Complexity: O(n)
Space Complexity: O(n)
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)$.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) |
| Prefix XOR Direct Computation | Time Complexity: O(n) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Approach | O(n) | O(1) | General case when reconstructing the array sequentially from prefix values |
| Prefix XOR Direct Computation | O(n) | O(1) | Best approach when leveraging XOR cancellation between consecutive prefix values |
Find The Original Array of Prefix Xor | XOR Properties | Microsoft | Leetcode - 2433 • codestorywithMIK • 9,617 views views
Watch 9 more video solutions →Practice Find The Original Array of Prefix Xor with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor