Watch 10 video solutions for Find The Original Array of Prefix Xor, a medium level problem involving Array, Bit Manipulation. This walkthrough by codestorywithMIK has 9,617 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |