Skip to content

Latest commit

 

History

History
196 lines (151 loc) · 4.23 KB

README_EN.md

File metadata and controls

196 lines (151 loc) · 4.23 KB
comments difficulty edit_url rating source tags
true
Medium
1366
Weekly Contest 314 Q2
Bit Manipulation
Array

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}

Rust

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
    }
}

C

/**
 * 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;
}