Difficulty: 🟡 Medium
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.
1 <= pref.length <= 105
0 <= pref[i] <= 106
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
answer= [pref[0]]
for i in range(len(pref)-1):
answer.append(pref[i]^pref[i+1])
return answer
The given solution constructs the array arr
based on the given pref
array by performing the bitwise XOR operation between adjacent elements.
The algorithm works as follows:
- Initialize an empty array
answer
with the first element ofpref
as the first element ofanswer
. - Iterate through the range from 0 to the length of
pref
minus 1:- Calculate the XOR of the current element in
pref
and the next element inpref
. - Append the result of the XOR operation to the
answer
array.
- Calculate the XOR of the current element in
- Return the
answer
array, which represents the arrayarr
that satisfies the given condition.
The algorithm constructs the answer
array by performing the bitwise XOR operation between adjacent elements of the pref
array.
The time complexity of this algorithm is O(n), where n is the size of the pref
array. The algorithm iterates through the pref
array once and performs a constant-time XOR operation at each iteration.
The space complexity of the algorithm is O(n) as it creates a new array, answer
, to store the elements of arr
.
The given solution constructs the array arr
based on the given pref
array by performing the bitwise XOR operation between adjacent elements. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.
NB: If you want to get community points please suggest solutions in other languages as merge requests.