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
Find Original Array from Prefix XORGiven: Prefix XOR Array52031Apply XOR Property: arr[i] = pref[i] ⊕ pref[i-1]Result: Original Array57232pref[0]2⊕5=70⊕2=23⊕0=31⊕3=2Verification: 5⊕7=2, 5⊕7⊕2=0, 5⊕7⊕2⊕3=3, 5⊕7⊕2⊕3⊕2=1 ✓
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
Asked in
Google 25 Amazon 20 Microsoft 15
28.0K Views
Medium Frequency
~12 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen