#2433
Medium Algorithms Find the original array of prefix xor
Array Bit Manipulation
88.3% acceptance
Feb 25, 2026
1504
91
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.
Solution
Rust
Time O(n)
Space O(n)
impl Solution {
pub fn find_array(pref: Vec<i32>) -> Vec<i32> {
let mut arr = vec![pref[0]];
for i in 1..pref.len() {
arr.push(pref[i] ^ pref[i - 1]);
}
arr
}
}