Find The Original Array of Prefix Xor

MEDIUM

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.

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

Constraints:

1 <= pref.length <= 10⁵
0 <= pref[i] <= 10⁶

Approaches

Checkout 3 different approaches to solve Find The Original Array of Prefix Xor. Click on different approaches to view the approach and algorithm in detail.

Brute-Force with Re-computation

This naive approach directly implements the definition of the prefix XOR array. To find each element arr[i], it re-computes the XOR sum of all previously found elements arr[0] through arr[i-1]. While correct, this method is computationally expensive.

Algorithm

Create a new integer array arr of the same size as pref.
If pref is not empty, set arr[0] = pref[0].
Iterate with a loop from i = 1 to pref.length - 1.
Inside the loop, calculate the prefix XOR of the already computed part of arr: prefixXorOfArr = arr[0] ^ arr[1] ^ ... ^ arr[i-1]. This requires a nested loop.
Calculate arr[i] = prefixXorOfArr ^ pref[i].
After the loop, return arr.

The fundamental relationship is pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]. From this, we can derive arr[i] = (arr[0] ^ arr[1] ^ ... ^ arr[i-1]) ^ pref[i]. The algorithm proceeds by building the arr array element by element. For each arr[i], it first iterates through arr[0] to arr[i-1] to calculate their XOR sum, and then XORs this sum with pref[i] to find arr[i]. This repetitive calculation of the prefix XOR for arr makes the approach inefficient.

class Solution {
    public int[] findArray(int[] pref) {
        int n = pref.length;
        if (n == 0) {
            return new int[0];
        }
        int[] arr = new int[n];
        arr[0] = pref[0];
        for (int i = 1; i < n; i++) {
            // Re-compute prefix XOR of arr
            int prefixXorOfArr = 0;
            for (int j = 0; j < i; j++) {
                prefixXorOfArr ^= arr[j];
            }
            arr[i] = prefixXorOfArr ^ pref[i];
        }
        return arr;
    }
}

Complexity Analysis

Time Complexity: O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times to re-compute the prefix XOR. This leads to a quadratic runtime.Space Complexity: O(n) - A new array of size `n` is created to store the result.

Pros and Cons

Pros:

It's a straightforward implementation of the mathematical definition, making it easy to conceptualize.

Cons:

Highly inefficient due to the nested loops, resulting in quadratic time complexity.
Will likely cause a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.

Code Solutions

Checking out 3 solutions in different languages for Find The Original Array of Prefix Xor. Click on different languages to view the code.

class Solution { public int [] findArray ( int [] pref ) { int n = pref . length ; int [] ans = new int [ n ]; ans [ 0 ] = pref [ 0 ]; for ( int i = 1 ; i < n ; ++ i ) { ans [ i ] = pref [ i - 1 ] ^ pref [ i ]; } return ans ; } }

Video Solution

Watch the video walkthrough for Find The Original Array of Prefix Xor

Patterns:

Bit Manipulation

Data Structures:

Array

Companies:

IBM |Morgan Stanley |Nvidia |