Find The Original Array of Prefix Xor - Problem
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.
Input & Output
Example 1 — Basic Case
$
Input:
pref = [5,2,0,3,1]
›
Output:
[5,7,2,3,2]
💡 Note:
arr[0]=5, arr[1]=pref[1]^pref[0]=2^5=7, arr[2]=pref[2]^pref[1]=0^2=2, arr[3]=pref[3]^pref[2]=3^0=3, arr[4]=pref[4]^pref[3]=1^3=2
Example 2 — Single Element
$
Input:
pref = [13]
›
Output:
[13]
💡 Note:
Single element case: arr[0] = pref[0] = 13
Example 3 — With Zeros
$
Input:
pref = [0,0,0]
›
Output:
[0,0,0]
💡 Note:
arr[0]=0, arr[1]=0^0=0, arr[2]=0^0=0. All elements are zero.
Constraints
- 1 ≤ pref.length ≤ 105
- 0 ≤ pref[i] ≤ 106
Visualization
Tap to expand
Understanding the Visualization
1
Input
Prefix XOR array: [5,2,0,3,1]
2
Process
Use XOR property to extract each element
3
Output
Original array: [5,7,2,3,2]
Key Takeaway
🎯 Key Insight: XOR is self-inverse, so we can extract each element by XORing consecutive prefix values
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code