Problem Description

You are given an integer array pref of size n, which represents a prefix XOR array. Your task is to find and return the original array arr of size n that was used to generate this prefix XOR array.

The relationship between pref and arr is defined as:

• pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

Where ^ denotes the bitwise XOR operation.

In other words, each element pref[i] is the XOR of all elements in arr from index 0 to index i (inclusive).

The problem guarantees that the answer is unique - there is exactly one array arr that can produce the given prefix XOR array pref.

To solve this problem, you need to work backwards from the prefix XOR array to reconstruct the original array. The key insight is that since XOR has the property that a ^ a = 0 and a ^ 0 = a, you can use the relationship between consecutive prefix values to find each element of the original array.

Specifically, since:

• pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
• pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]

By XORing these two values: pref[i] ^ pref[i-1] = arr[i]

This works because all the common terms (arr[0] through arr[i-1]) cancel out when XORed with themselves, leaving only arr[i].

Intuition

The key to understanding this problem lies in the properties of the XOR operation. XOR has two crucial properties that help us here:

1. a ^ a = 0 (any number XORed with itself equals 0)
2. a ^ 0 = a (any number XORed with 0 equals itself)

Let's think about what we know and what we need to find. We're given the prefix XOR array where each element represents the cumulative XOR up to that index. We need to recover the original array that produced these prefix values.

Consider a simple example to build intuition. If we have arr = [a, b, c], then:

• pref[0] = a
• pref[1] = a ^ b
• pref[2] = a ^ b ^ c

Now, how can we recover arr from pref?

For the first element, it's straightforward: arr[0] = pref[0] since pref[0] is just arr[0] by itself.

For the second element, we need to extract b from pref[1] = a ^ b. Since we know a (which is pref[0]), we can XOR both sides with a:

• pref[1] ^ a = (a ^ b) ^ a = b ^ (a ^ a) = b ^ 0 = b
• So arr[1] = pref[1] ^ pref[0]

Following this pattern, for any element at index i:

• We have pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]
• We also have pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]
• If we XOR these two expressions: pref[i] ^ pref[i-1], all the common terms cancel out due to the a ^ a = 0 property
• This leaves us with just arr[i]

This gives us the formula: arr[i] = pref[i] ^ pref[i-1]

For implementation convenience, we can think of pref[-1] = 0 (before the array starts, the XOR is 0), which makes the formula work uniformly for all indices including index 0.

Solution Approach

Based on our intuition, we can implement the solution using the formula we derived: arr[i] = pref[i] ^ pref[i-1].

The implementation uses a clever Python approach with the pairwise function to create pairs of consecutive elements. Here's how it works:

1. Prepend 0 to the prefix array: We create [0] + pref to handle the base case. This represents pref[-1] = 0, which allows us to compute arr[0] = pref[0] ^ 0 = pref[0].

2. Create consecutive pairs: The pairwise function takes [0] + pref and creates pairs of consecutive elements:

   • First pair: (0, pref[0])
   • Second pair: (pref[0], pref[1])
   • Third pair: (pref[1], pref[2])
   • And so on...

3. Apply XOR to each pair: Using list comprehension, we XOR each pair (a, b) where:

   • a represents pref[i-1] (or 0 for the first element)
   • b represents pref[i]
   • a ^ b gives us arr[i]

The one-line solution [a ^ b for a, b in pairwise([0] + pref)] elegantly captures this entire process:

• It handles all indices uniformly without special cases
• It directly applies the mathematical relationship we derived
• It returns the reconstructed array in a single pass with O(n) time complexity

For example, if pref = [5, 7, 2]:

• We create [0, 5, 7, 2]
• Pairs: (0, 5), (5, 7), (7, 2)
• XOR results: 0^5=5, 5^7=2, 7^2=5
• Original array: [5, 2, 5]

This approach is both efficient and elegant, leveraging Python's built-in functions to solve the problem in a single line while maintaining O(n) time and O(1) extra space complexity (excluding the output array).

Example Walkthrough

Let's walk through a concrete example to see how we reconstruct the original array from a prefix XOR array.

Given: pref = [5, 7, 2, 10]

We need to find the original array arr such that:

• pref[0] = arr[0] = 5
• pref[1] = arr[0] ^ arr[1] = 7
• pref[2] = arr[0] ^ arr[1] ^ arr[2] = 2
• pref[3] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3] = 10

Step 1: Prepend 0 to handle the base case

• Modified array: [0, 5, 7, 2, 10]

Step 2: Create consecutive pairs

• Pair 1: (0, 5)
• Pair 2: (5, 7)
• Pair 3: (7, 2)
• Pair 4: (2, 10)

Step 3: XOR each pair to get original array elements

For arr[0]:

• XOR pair (0, 5) → 0 ^ 5 = 5
• Therefore arr[0] = 5

For arr[1]:

• XOR pair (5, 7) → 5 ^ 7 = 2
• Therefore arr[1] = 2
• Verification: arr[0] ^ arr[1] = 5 ^ 2 = 7 ✓ (matches pref[1])

For arr[2]:

• XOR pair (7, 2) → 7 ^ 2 = 5
• Therefore arr[2] = 5
• Verification: arr[0] ^ arr[1] ^ arr[2] = 5 ^ 2 ^ 5 = 2 ✓ (matches pref[2])

For arr[3]:

• XOR pair (2, 10) → 2 ^ 10 = 8
• Therefore arr[3] = 8
• Verification: arr[0] ^ arr[1] ^ arr[2] ^ arr[3] = 5 ^ 2 ^ 5 ^ 8 = 10 ✓ (matches pref[3])

Result: arr = [5, 2, 5, 8]

The solution leverages the fact that pref[i] ^ pref[i-1] cancels out all common terms from indices 0 to i-1, leaving only arr[i]. This works because XOR is self-inverse: any value XORed with itself equals 0.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the prefix XOR array pref. The pairwise function creates pairs from the list [0] + pref, which has length n + 1, resulting in n pairs. The list comprehension iterates through all these pairs exactly once, performing a constant-time XOR operation a ^ b for each pair.

The space complexity is O(1) if we exclude the space required for the output array. The pairwise function returns an iterator that generates pairs on-the-fly without creating an intermediate list. The only additional space used is for the temporary variables a and b in the list comprehension, which is constant. However, if we include the output array in the space complexity analysis, it would be O(n) since we're creating a new list of size n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling the First Element

A common mistake is trying to compute arr[0] by accessing pref[-1], which would cause an index error. Many developers write something like:

# WRONG - This will cause IndexError for i=0
arr = []
for i in range(len(pref)):
    arr.append(pref[i] ^ pref[i-1])  # Error when i=0

Solution: Always handle the first element as a special case, either by checking the index or prepending 0 to the array:

# Correct approach 1: Special case for first element
arr = [pref[0]]  # arr[0] = pref[0] ^ 0 = pref[0]
for i in range(1, len(pref)):
    arr.append(pref[i] ^ pref[i-1])

# Correct approach 2: Prepend 0 (as shown in the solution)
return [a ^ b for a, b in pairwise([0] + pref)]

2. Misunderstanding the XOR Cancellation Property

Some developers incorrectly think they need to XOR all previous elements to get the current element, leading to inefficient O(n²) solutions:

# WRONG - Inefficient and incorrect logic
arr = []
for i in range(len(pref)):
    current = pref[i]
    for j in range(i):
        current ^= arr[j]  # This is NOT how to recover arr[i]
    arr.append(current)

Solution: Remember that pref[i] ^ pref[i-1] directly gives arr[i] due to XOR's self-inverse property. You only need to XOR consecutive prefix values, not reconstruct from scratch.

3. Off-by-One Errors in Manual Iteration

When manually iterating without using pairwise, it's easy to create off-by-one errors:

# WRONG - Creates array with wrong length
arr = []
for i in range(len(pref) - 1):  # Missing last element!
    if i == 0:
        arr.append(pref[0])
    else:
        arr.append(pref[i] ^ pref[i-1])

Solution: Ensure your loop covers all indices from 0 to len(pref)-1:

# Correct manual iteration
arr = []
for i in range(len(pref)):
    if i == 0:
        arr.append(pref[0])
    else:
        arr.append(pref[i] ^ pref[i-1])

4. Modifying the Input Array

Some developers try to modify the input array in-place to save space, which can lead to incorrect results:

# WRONG - Modifying pref while reading from it
for i in range(len(pref) - 1, 0, -1):
    pref[i] = pref[i] ^ pref[i-1]  # This destroys the data needed for next iteration
return pref

Solution: Either create a new array for the result or carefully process from right to left if modifying in-place:

# Correct in-place modification (process right to left)
for i in range(len(pref) - 1, 0, -1):
    pref[i] ^= pref[i-1]
# pref[0] remains unchanged (arr[0] = pref[0])
return pref