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.

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 |