##### 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).