## [2433. Find The Original Array of Prefix Xor](https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/)

# 1. Tóm tắt đề bài

Bạn cần phải tìm một mảng $arr$ có $n$ phần tử, biết giá trị của mảng $pref$. $pref[i]$ được định nghĩa là [tổng $XOR$](https://www.loginradius.com/blog/engineering/how-does-bitwise-xor-work/) của $i$ phần tử đầu tiên trong dãy.

##### Giới hạn

$1 \le n \le 10^5$.
$1 \le pref[i] \le 10^6$.

# 2. Tiếp cận lời giải

**Độ phức tạp dự tính: $O(n)$**.

Ta vận dụng tính chất của phép toán $XOR$, ký hiệu là $\oplus$:

Nếu $a \oplus b = c$ ta có thể suy ra $a \oplus c = b$ và $c \oplus b = a$.

Dựa vào cách tính của hàm $pref$, ta có $pref[i] = pref[i - 1] \oplus arr[i]$. Từ đây, suy ra:

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

# 3. Lời giải chi tiết

Sau khi rút ra nhận xét như phần tiếp cận, phần còn lại không quá khó để lập trình.

Code mẫu: https://leetcode.com/problems/find-the-original-array-of-prefix-xor/submissions/1087982511/

### Độ phức tạp thuật toán

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(1)$

# 4. Kết luận & Gợi ý mở rộng

Bài không khó, nhưng yêu cầu các bạn nắm chắc phần [các phép toán bitwise](https://vnoi.info/wiki/algo/basic/bitwise-operators.md). Hãy coi như đây là một trong những bài cơ bản nhé!