Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2433.html
2433. Find The Original Array of Prefix Xor
- Difficulty: Medium.
- Related Topics: Array, Bit Manipulation.
- Similar Questions: Single Number III, Count Triplets That Can Form Two Arrays of Equal XOR, Decode XORed Array.
Problem
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.
Constraints:
-
1 <= pref.length <= 10^5
-
0 <= pref[i] <= 10^6
Solution (Java, C++, Python)
-
class Solution { public int[] findArray(int[] pref) { int n = pref.length; int[] ans = new int[n]; ans[0] = pref[0]; for (int i = 1; i < n; ++i) { ans[i] = pref[i - 1] ^ pref[i]; } return ans; } }
-
class Solution { public: vector<int> findArray(vector<int>& pref) { int n = pref.size(); vector<int> ans = {pref[0]}; for (int i = 1; i < n; ++i) { ans.push_back(pref[i - 1] ^ pref[i]); } return ans; } };
-
class Solution: def findArray(self, pref: List[int]) -> List[int]: ans = [pref[0]] for a, b in pairwise(pref): ans.append(a ^ b) return ans
-
func findArray(pref []int) []int { n := len(pref) ans := []int{pref[0]} for i := 1; i < n; i++ { ans = append(ans, pref[i-1]^pref[i]) } return ans }
-
function findArray(pref: number[]): number[] { let ans = pref.slice(); for (let i = 1; i < pref.length; i++) { ans[i] = pref[i - 1] ^ pref[i]; } return ans; }
-
impl Solution { pub fn find_array(pref: Vec<i32>) -> Vec<i32> { let n = pref.len(); let mut res = vec![0; n]; res[0] = pref[0]; for i in 1..n { res[i] = pref[i] ^ pref[i - 1]; } res } }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).