Scale Engineer

Find The Original Array of Prefix Xor

Med
#2217Time: 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: O(n) - A new array of size `n` is created to store the result.3 companies
Patterns
Bit Manipulation
Data structures
Array
Companies
IBMMorgan StanleyNvidia

Prompt

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 <= 105
  • 0 <= pref[i] <= 106

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(n) - A new array of size `n` is created to store the result.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem