Skip to content

2433. Find The Original Array of Prefix Xor

Description

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 <= 105
  • 0 <= pref[i] <= 106

Solutions

Solution 1: Bit Manipulation

According to the problem statement, we have equation one:

\[ pref[i]=arr[0] \oplus arr[1] \oplus \cdots \oplus arr[i] \]

So, we also have equation two:

\[ pref[i-1]=arr[0] \oplus arr[1] \oplus \cdots \oplus arr[i-1] \]

We perform a bitwise XOR operation on equations one and two, and get:

\[ pref[i] \oplus pref[i-1]=arr[i] \]

That is, each item in the answer array is obtained by performing a bitwise XOR operation on the adjacent two items in the prefix XOR array.

The time complexity is \(O(n)\), where \(n\) is the length of the prefix XOR array. Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

1
2
3
class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        return [a ^ b for a, b in pairwise([0] + pref)]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
7
8
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
}

1
2
3
4
5
6
7
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findArray(int* pref, int prefSize, int* returnSize) {
    int* res = (int*) malloc(sizeof(int) * prefSize);
    res[0] = pref[0];
    for (int i = 1; i < prefSize; i++) {
        res[i] = pref[i - 1] ^ pref[i];
    }
    *returnSize = prefSize;
    return res;
}

Comments