2433. Find The Original Array of Prefix Xor
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.
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 becausepref[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 listpref
. -
These pairs are generated using the
pairwise
utility, which groups every two adjacent items together. Sincepairwise
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 withoutpairwise
would look like this:[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 elementpref[i]
with its previous elementpref[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 thepref
list. This is a critical step because it allows us to obtain the first element ofarr
(which is equal topref[0]
) without changing the algorithm. For subsequent elements, we use the XOR operation to derive them from the cumulative XOR values inpref
. -
To demonstrate the XOR operation's effect, consider
pref
to be[1, 2, 3]
. After prepending a0
, it becomes[0, 1, 2, 3]
. When we apply pairwise XOR as per the solution, we getarr
as follows:arr[0] = 0 ^ 1 = 1 arr[1] = 1 ^ 2 = 3 arr[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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach. Suppose we are given the following pref
array:
pref = [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:
arr[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:
arr[1] = pref[0] ^ pref[1] = 5 ^ 1 = 4
We continue this process to find arr[2]
:
arr[2] = pref[1] ^ pref[2] = 1 ^ 7 = 6
Now we have constructed the array arr
:
arr = [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]
is5
, which matchespref[0]
. - For
i = 1
:arr[0] ^ arr[1]
equals5 ^ 4
, which is1
, matchingpref[1]
. - For
i = 2
:arr[0] ^ arr[1] ^ arr[2]
equals5 ^ 4 ^ 6
, which is7
, matchingpref[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:
- Initialize the
arr
array by settingarr[0]
topref[0]
. - Iterate through the
pref
array from index1
ton-1
, wheren
is the number of elements inpref
. - Calculate
arr[i]
using the formulaarr[i] = pref[i-1] ^ pref[i]
for eachi
. - The resultant
arr
array will have the same size aspref
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
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.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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
Want a Structured Path to Master System Design Too? Donāt Miss This!