LeetCode 2433 - Find The Original Array of Prefix Xor

LeetCode Problem 2433

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem is asking us to reverse-engineer an array arr from its prefix XOR array pref. Specifically, pref[i] represents the XOR of all elements in arr from index 0 to i. Our goal is to reconstruct arr given only pref.

For instance, if pref = [5,2,0,3,1], it means:

• pref[0] = arr[0]
• pref[1] = arr[0] ^ arr[1]
• pref[2] = arr[0] ^ arr[1] ^ arr[2]
• pref[3] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3]
• pref[4] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3] ^ arr[4]

The expected output is the array arr that satisfies these equations.

The constraints 1 <= pref.length <= 10^5 and 0 <= pref[i] <= 10^6 tell us that the solution must be linear in time and space to handle large arrays efficiently. Important edge cases include a single-element array and arrays where elements XOR to zero.

The problem guarantees that the answer is unique, so we do not need to consider multiple valid solutions.

Approaches

Brute Force Approach

A naive brute-force approach would try all possible sequences for arr that produce the given pref by using backtracking. At each step, you would try to pick a number that, when XORed with the cumulative XOR so far, equals the next pref[i]. While this would eventually find a solution, it is extremely inefficient and infeasible for n up to 10^5, because it explores an exponential search space.

Optimal Approach

The key observation for an optimal solution comes from the properties of XOR. If pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i], then:

• arr[0] = pref[0]
• arr[1] = pref[0] ^ pref[1]
• arr[2] = pref[1] ^ pref[2]
• arr[i] = pref[i-1] ^ pref[i] for i >= 1

This works because XOR is its own inverse: if x ^ y = z, then y = x ^ z. So, we can reconstruct arr in a single pass by XORing consecutive elements of pref.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries all possible sequences, infeasible for large n
Optimal	O(n)	O(n)	Uses XOR property to reconstruct arr directly

Algorithm Walkthrough

1. Initialize an empty array arr of the same length as pref.
2. Set the first element of arr to be pref[0] because arr[0] is always equal to pref[0].
3. Iterate from i = 1 to n-1:

• Compute arr[i] as pref[i] ^ pref[i-1]. This works because arr[0] ^ ... ^ arr[i] ^ arr[0] ^ ... ^ arr[i-1] = arr[i].

4. Return the reconstructed arr.

Why it works: XOR is reversible and associative. By XORing consecutive prefix XORs, we cancel out all previous elements, leaving only the current element. This ensures that each arr[i] is correctly calculated.

Python Solution

from typing import List

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        n = len(pref)
        arr = [0] * n
        arr[0] = pref[0]
        for i in range(1, n):
            arr[i] = pref[i] ^ pref[i - 1]
        return arr

Implementation Walkthrough: We first allocate arr and assign its first element directly from pref[0]. Then we loop through the remaining indices and XOR each consecutive pref pair to determine the next element in arr. This directly implements the XOR property described in the algorithm walkthrough.

Go Solution

func findArray(pref []int) []int {
    n := len(pref)
    arr := make([]int, n)
    arr[0] = pref[0]
    for i := 1; i < n; i++ {
        arr[i] = pref[i] ^ pref[i-1]
    }
    return arr
}

Go Implementation Notes: The Go version mirrors the Python logic. We use make to initialize the slice. Go handles integers without special care for overflow since constraints guarantee values fit in 32-bit integers. The loop logic is identical to Python.

Worked Examples

Example 1: pref = [5,2,0,3,1]

i	pref[i]	arr[i] calculation	arr
0	5	arr[0] = pref[0]	[5]
1	2	arr[1] = 5 ^ 2 = 7	[5,7]
2	0	arr[2] = 2 ^ 0 = 2	[5,7,2]
3	3	arr[3] = 0 ^ 3 = 3	[5,7,2,3]
4	1	arr[4] = 3 ^ 1 = 2	[5,7,2,3,2]

Example 2: pref = [13]

i	pref[i]	arr[i]
0	13	13

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the pref array
Space	O(n)	Storing the resulting array arr

This is efficient enough to handle the maximum constraint n = 10^5.

Test Cases

# Single element
assert Solution().findArray([13]) == [13]  # simplest case

# Example from problem statement
assert Solution().findArray([5,2,0,3,1]) == [5,7,2,3,2]

# Increasing numbers with XOR
assert Solution().findArray([1,3,0,4]) == [1,2,3,4]

# All zeros
assert Solution().findArray([0,0,0,0]) == [0,0,0,0]

# Alternating pattern
assert Solution().findArray([1,0,1,0]) == [1,1,1,1]

# Large array stress test
assert Solution().findArray([i ^ (i-1) for i in range(1, 100001)]) == [0] + [i for i in range(1,100001)]

Test	Why
[13]	Single-element array edge case
[5,2,0,3,1]	Example given in problem statement
[1,3,0,4]	Checks generic XOR calculation
[0,0,0,0]	All zeros case, ensures no negative or incorrect XORs
[1,0,1,0]	Alternating XOR pattern, tests small toggling
Large array	Tests performance and correctness for maximum constraints

Edge Cases

1. Single-element array: The simplest case where pref has length 1. This verifies that the code handles minimal input without indexing errors. The implementation handles this by directly assigning arr[0] = pref[0].
2. All elements zero: A pref array of all zeros ensures that the XOR calculations do not introduce unintended non-zero values. Since 0 ^ 0 = 0, the algorithm correctly reconstructs an array of zeros.
3. Large array with maximum constraints: A pref array with 10^5 elements tests both performance and correctness. Using a linear O(n) algorithm ensures that the program executes efficiently without exceeding memory limits. The algorithm does not rely on recursion or backtracking, avoiding stack overflow.