Skip to content

2433. Find The Original Array of Prefix Xor

SourceWeekly Contest 314 Q2DifficultyMediumRating1366

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

Thinking

\(\textit{pref}[i]\) is the XOR of \(\textit{arr}[0..i]\). Then \(\textit{pref}[i]\oplus \textit{pref}[i-1]=\textit{arr}[i]\) with \(\textit{pref}[-1]=0\), so the original array is the adjacent-prefix XOR. One linear pass at \(n\le 10^5\).

According to the problem statement, we have equation one:

\[ \textit{pref}[i]=\textit{arr}[0] \oplus \textit{arr}[1] \oplus \cdots \oplus \textit{arr}[i] \]

So, we also have equation two:

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

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

\[ \textit{pref}[i] \oplus \textit{pref}[i-1]=\textit{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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the prefix XOR array.

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