Sponsored
Sponsored
This approach involves iterating through the prefix XOR array and using the properties of XOR to deduce the original array. Starting from the first element, which is the same as in the original array, subsequent elements can be found using the formula:
arr[i] = pref[i] ^ pref[i-1]
since pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] and pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1].
Time Complexity: O(n)
Space Complexity: O(n)
1def findArray(pref):
2 arr = [pref[0]]
3 for i in range(1, len(pref)):
4 arr.append(pref[i] ^ pref[i - 1])
5 return arr
6
7pref = [5, 2, 0, 3, 1]
8arr = findArray(pref)
9print(arr)Utilizing Python's list operations, this solution iteratively applies XOR on consecutive elements of the prefix array to derive the original array elements. The usage of Python's simple iteration and list manipulation makes the solution concise and readable.
This approach calculates each element of the original array directly by using the property of XOR that makes it its own inverse. By understanding that the difference between consecutive prefix values gives the desired element, this method is implemented in a direct computational manner.
Time Complexity: O(n)
Space Complexity: O(n)
1
In this Python version, we compute the original array by realizing that each element after the first is the XOR of consecutive prefix elements. This concise function demonstrates Python's capabilities of handling such operations efficiently in a compact form.