2433. Find The Original Array of Prefix Xor

MediumBit ManipulationArray
Leetcode Link

Problem Description

You are given an array of integers named pref that has a length of n. Your task is to find and return another integer array called arr that also has the size n. This arr array should meet a specific requirement: Each element at index i in the pref array must be equal to the cumulative bitwise XOR of elements from 0 to i in the arr array. The bitwise XOR operation is represented by the ^ symbol and combines bits where the result is 1 if only one of the bits compared is 1, and 0 otherwise.

For example, if pref[i] equals 5, it means that arr[0] ^ arr[1] ^ ... ^ arr[i] must also be equal to 5.

It's important to note that there is only one unique solution to this problem. Your goal is to construct the arr array that will satisfy the given condition for each element in pref.

Intuition

Now let's think about how to arrive at the solution. The key observation here is to recognize the properties of the XOR operation. One crucial property of XOR is that it is self-inverse, meaning that for any number x, we have x ^ x = 0. So, if we XOR a number with itself, we get 0.

Given the definition of pref[i] as arr[0] ^ arr[1] ^ ... ^ arr[i], we can deduce arr[i] using pref[i - 1] and pref[i]. Because if we have pref[i-1] as arr[0] ^ arr[1] ^ ... ^ arr[i-1], then pref[i] = (arr[0] ^ arr[1] ^ ... ^ arr[i-1]) ^ arr[i]. Now if we XOR pref[i-1] with pref[i], we can isolate arr[i] because (arr[0] ^ ... ^ arr[i-1]) ^ (arr[0] ^ ... ^ arr[i-1] ^ arr[i]) will cancel out all terms except arr[i].

Hence, we start with arr[0] which is just pref[0] since arr[0] exclusively XORed with nothing is arr[0]. Then, for subsequent elements, we calculate arr[i] as pref[i-1] ^ pref[i].

The Python code provided uses a list comprehension that takes pairs of elements from [0] + pref (we add a 0 at the beginning for convenience in calculating arr[0]) and performs the XOR operation between adjacent elements of pref. The pairwise utility generates pairs of elements from the given list, which the list comprehension processes. The function returns the constructed arr list that meets the condition defined by the pref array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the maximum element can be found in:

Solution Approach

The solution involves a simple but clever use of properties of the XOR operation in combination with Python's built-in functions. Let's break down the implementation step-by-step to understand it better.

  • First, is the initialization of the result array. The first element of arr can immediately be determined because pref[0] = arr[0]. Therefore, no calculation is needed for the first element.

  • Then we use a list comprehension to build the rest of the arr array. List comprehensions are a concise way to create lists in Python, and in this case, it is used to iterate through pairs of elements from the input list pref.

  • These pairs are generated using the pairwise utility, which groups every two adjacent items together. Since pairwise is not a default function in Python, it is assumed to be a hypothetical utility that would perform this action. A more accurate Python code to achieve the same without pairwise would look like this:

    1[pref[i] ^ pref[i-1] for i in range(1, len(pref))]

    This code iterates over the pref array from the second element to the last, XORing each element pref[i] with its previous element pref[i-1]. The iteration starts from 1 because we are interested in pairs and the first element is already processed.

  • Before executing the XOR operation, we prepare the list by adding a 0 to the beginning of the pref list. This is a critical step because it allows us to obtain the first element of arr (which is equal to pref[0]) without changing the algorithm. For subsequent elements, we use the XOR operation to derive them from the cumulative XOR values in pref.

  • To demonstrate the XOR operation's effect, consider pref to be [1, 2, 3]. After prepending a 0, it becomes [0, 1, 2, 3]. When we apply pairwise XOR as per the solution, we get arr as follows:

    1arr[0] = 0 ^ 1 = 1
2arr[1] = 1 ^ 2 = 3
3arr[2] = 2 ^ 3 = 1

    Hence, arr = [1, 3, 1].

  • Finally, by iterating through these pairs, we XOR them to reconstruct each element of arr and derive the singular unique solution as proven by the properties of XOR.

In essence, the algorithm relies heavily on the understanding of how XOR functions as an associative and commutative operation, and on Python's ability to elegantly iterate through elements and perform operations using list comprehensions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's take a small example to illustrate the solution approach. Suppose we are given the following pref array:

1pref = [5, 1, 7]

Our goal is to construct an arr array such that pref[i] equals the cumulative XOR from arr[0] to arr[i].

We start by setting arr[0] to pref[0] because there are no previous elements to XOR with, as described in the Intuition section. Thus:

1arr[0] = pref[0] = 5

Next, we need to determine arr[1]. We use the fact that pref[1] is the XOR of arr[0] and arr[1]. Since pref[1] is 1 and arr[0] is 5, we can isolate arr[1] as follows:

1arr[1] = pref[0] ^ pref[1] = 5 ^ 1 = 4

We continue this process to find arr[2]:

1arr[2] = pref[1] ^ pref[2] = 1 ^ 7 = 6

Now we have constructed the array arr:

1arr = [5, 4, 6]

Let's verify that this arr satisfies the original problem conditions. To do this, we check the cumulative XOR for each index i in arr:

  • For i = 0: arr[0] is 5, which matches pref[0].
  • For i = 1: arr[0] ^ arr[1] equals 5 ^ 4, which is 1, matching pref[1].
  • For i = 2: arr[0] ^ arr[1] ^ arr[2] equals 5 ^ 4 ^ 6, which is 7, matching pref[2].

As we can see, each pref[i] is equal to the cumulative XOR of elements from 0 to i in the constructed arr, validating our solution.

To summarize the steps:

  1. Initialize the arr array by setting arr[0] to pref[0].
  2. Iterate through the pref array from index 1 to n-1, where n is the number of elements in pref.
  3. Calculate arr[i] using the formula arr[i] = pref[i-1] ^ pref[i] for each i.
  4. The resultant arr array will have the same size as pref and will meet the required condition.

By following this approach, we have successfully solved the problem by understanding the behavior of the XOR operation and applying it systematically.

Solution Implementation

1# The following import is necessary to use the pairwise utility.
2# It creates an iterator that returns consecutive pairs of elements from the input.
3from itertools import pairwise
4
5class Solution:
6    def find_array(self, pref):
7        # Initialize an array with a leading zero that will be used
8        # for computing the original array based on the prefix XOR array.
9        orig_array_with_zero = [0] + pref
10      
11        # Compute the original array by XORing each consecutive pair of elements.
12        # This reverses the prefix XOR operation since a^a=0 and a^0=a.
13        # The resulting array is the original array that was used to compute
14        # the prefix XOR array.
15        orig_array = [a ^ b for a, b in pairwise(orig_array_with_zero)]
16      
17        return orig_array
18
19# An example usage:
20# If pref = [1, 3, 5]
21# The Solution().find_array(pref) will return the original array [1, 2, 7].
22
1class Solution {
2
3    // Method to find the original array from its prefix XOR array
4    public int[] findArray(int[] prefixXorArray) {
5        // Number of elements in the prefix XOR array
6        int length = prefixXorArray.length;
7
8        // Initialize the array to store the original array elements
9        int[] originalArray = new int[length];
10
11        // The first element of the original array is the same as the first element of the prefix XOR array
12        originalArray[0] = prefixXorArray[0];
13
14        // Iterate through the prefix XOR array starting from the second element
15        for (int i = 1; i < length; ++i) {
16            // Each element of the original array is obtained by XORing the current and previous elements of the prefix XOR array
17            originalArray[i] = prefixXorArray[i - 1] ^ prefixXorArray[i];
18        }
19
20        // Return the original array
21        return originalArray;
22    }
23}
24
1#include <vector> // Required for using the std::vector
2
3class Solution {
4public:
5    // Function to find the original array from its prefix XOR array.
6    std::vector<int> findArray(std::vector<int>& prefixXor) {
7        // The size of the prefix XOR array.
8        int size = prefixXor.size();
9      
10        // Initialize the resultant array with the first element from prefixXor,
11        // since the first element of both the original and prefix XOR arrays would be the same.
12        std::vector<int> originalArray = {prefixXor[0]};
13      
14        // Iterating over the prefixXor array starting from the second element.
15        for (int i = 1; i < size; ++i) {
16            // The current original array element is the XOR of the previous and current elements
17            // in the prefixXor array because the prefixXor[i] represents the XOR of all elements
18            // in originalArray from 0 to i, so "undoing" the previous XOR (prefixXor[i-1]) will
19            // give us the original value.
20            originalArray.push_back(prefixXor[i - 1] ^ prefixXor[i]);
21        }
22      
23        // Return the fully populated originalArray.
24        return originalArray;
25    }
26};
27
1function findArray(prefixArray: number[]): number[] {
2    // Create a copy of the prefixArray to hold the answer.
3    let answerArray = prefixArray.slice();
4
5    // Iterate over the prefixArray starting from index 1, as the first element 
6    // doesn't change (ans[0] = pref[0] since XOR with 0 is a no-op).
7    for (let i = 1; i < prefixArray.length; i++) {
8        // XOR the current element with the previous element of prefixArray
9        // and store the result in the answerArray, effectively computing the 
10        // original array before the prefix sums.
11        answerArray[i] = prefixArray[i - 1] ^ prefixArray[i];
12    }
13
14    // Return the resultant array after reversing the prefix sum operation.
15    return answerArray;
16}
17
18// Example usage:
19// const result = findArray([1,3,2,3]); // Should return [1,2,0,1]
20
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

Time and Space Complexity

The given code snippet implements a function to find an array from its prefix XOR array. The time and space complexities of the code can be analyzed as follows:

Time Complexity

The time complexity is O(n), where n is the length of the input pref array. This is because the function executes a single loop through the pref array plus an extra element (0 appended to the front), performing a constant-time XOR operation for each pair of elements.

Space Complexity

The space complexity of the function is O(n) as well, because it creates a new list with the same number of elements as the input list. This new list is populated with the results of the XOR operations between adjacent elements of the extended list [0] + pref.

In the case of the pairwise function, which is usually imported from the itertools module (not explicitly shown in the code), if it is implemented in such a way that it yields pairs of elements on-the-fly without creating a separate list or collection for them, the additional space overhead is O(1) (constant space). However, the resulting list still retains the time complexity of O(n) and space complexity of O(n) due to the reasons mentioned above.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫