You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

$text{pref}[i] = text{arr}[0] oplus text{arr}[1] oplus ldots oplus text{arr}[i]

It is guaranteed that a unique arr exists.

Examples

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation:
  pref[0] = 5             → arr[0] = 5
  pref[1] = 5 ^ 7 = 2    → arr[1] = 7
  pref[2] = 5 ^ 7 ^ 2 = 0 → arr[2] = 2
  ...

Example 2:

Input: pref = [13]
Output: [13]

Constraints

  • 1 <= n <= 10^5
  • 0 <= pref[i] <= 10^6

Thinking Process

XOR Prefix Sum Property

Given:

text{pref}[i] = text{arr}[0] oplus text{arr}[1] oplus ldots oplus text{arr}[i]

text{pref}[i-1] = text{arr}[0] oplus text{arr}[1] oplus ldots oplus text{arr}[i-1]

XOR both sides:

text{pref}[i] oplus text{pref}[i-1] = text{arr}[i]

This is the XOR analog of prefix sum difference: just as arr[i] = prefixSum[i] - prefixSum[i-1] for addition, we have arr[i] = pref[i] ^ pref[i-1] for XOR.

Base case: arr[0] = pref[0].

Bit manipulation 1 0 1 1 0 1 0 XOR pairs · masks · shifts

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
XOR tricks (this problem) O(n) O(1) Single number, swap without temp
Bit masks O(2^n) O(n) Subset enumeration
Brian Kernighan O(\log n) O(1) Count set bits
Shift operations O(n) O(1)$ Power of two, divide by 2

Solution

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> arr;
        arr.push_back(pref[0]);
        for (int i = 1; i < n; ++i) {
            arr.push_back(pref[i] ^ pref[i - 1]);
        }
        return arr;
    }
};

Solution Explanation

Approach: XOR tricks (this problem)

Key idea: ### XOR Prefix Sum Property

Walkthrough — input pref = [5,2,0,3,1], expected output [5,7,2,3,2]:

pref[0] = 5 → arr[0] = 5 pref[1] = 5 ^ 7 = 2 → arr[1] = 7 pref[2] = 5 ^ 7 ^ 2 = 0 → arr[2] = 2 …

Common Mistakes

  • Processing left-to-right in-place (corrupts values needed for later computations)
  • Forgetting the base case arr[0] = pref[0]

Key Takeaways

  • XOR prefix ↔ original array mirrors addition prefix sum ↔ difference array, with XOR replacing both addition and subtraction (since a ^ a = 0)
  • In-place reverse pass avoids the dependency issue cleanly
  • XOR is its own inverse: a ^ b ^ b = a – this self-inverse property underpins all XOR prefix problems

References

Template Reference