Introduction
In this problem, we are given an integer array pref of size n. Our objective is to find and return the array arr of size n that satisfies the condition: pref[i] = arr[0] ^ arr[1] ^ … ^ arr[i]. Here, ^ denotes the bitwise-xor operation. It’s also given that the answer is unique, which is a hint that there’s a deterministic way to solve this problem.
Intuition
To grasp the solution’s logic, one must first understand the properties of the XOR operation. The XOR operation has a unique property: for any number a, a ^ a = 0 and a ^ 0 = a. This property will be the cornerstone of our approach.
Given the problem’s constraints, we can infer that the first element of the original array arr[0] is simply pref[0]. For the subsequent elements, we can obtain them using the XOR of the current prefix and the previous prefix.
Code
In the code below, res initially holds the value of the first element of the pref array. For every subsequent element, we XOR the current prefix with the accumulated result (res) to obtain the current element of the original array. We then update res by XORing it with the current element of the original array.
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
res = pref[0]
for i in range(1, len(pref)):
pref[i] ^= res
res ^= pref[i]
return pref
Conclusion
Time Complexity: O(n)
The solution iterates through the pref array once, so the time complexity is O(n), where n is the size of the pref array.
Space Complexity: O(1)
We’re using a constant amount of extra space, irrespective of the input size. Thus, the space complexity is O(1).
Conclusion:
This problem is a great example of how understanding the properties and characteristics of certain operations (in this case, the XOR operation) can help in devising efficient solutions. The given solution is both time-efficient and space-efficient. By iterating through the pref array just once and leveraging the properties of XOR, we can reconstruct the original array in a straightforward manner.