Find The Original Array of Prefix Xor

Problem Description

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.

Key Insights

• The value of arr[i] can be derived using the prefix XOR values.
• The relationship can be expressed as:
  • arr[i] = pref[i] ^ pref[i - 1] for i > 0
  • arr[0] = pref[0] for the first element.
• XOR operation has a unique property: a ^ a = 0 and a ^ 0 = a, which allows us to reconstruct the original array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will:

1. Initialize an array arr of the same size as pref.
2. Set the first element of arr equal to the first element of pref.
3. For each subsequent index i, compute arr[i] using the formula: arr[i] = pref[i] ^ pref[i - 1].
4. Return the resulting array.

This approach uses a single pass through the pref array, ensuring efficiency.

Code Solutions