Bài toán
Link đến bài toán: 2433. Find The Original Array of Prefix Xor
Phân tích
Bài này không khó đâu. Kiến thức cần biết để làm bài này là:
a ^ b = c
=> a ^ c = b
=> b ^ c = a
Theo dề bài:
pref[i] = pref[i-1] ^ arr[i]
=> arr[i] = pref[i] ^ pref[i-1]
Vậy ta loop qua pref
và tính arr[i]
rồi thêm vào mảng arr
là xong.
Giải thuật
func findArray(pref []int) []int {
n := len(pref)
arr := make([]int, n)
arr[0] = pref[0]
for i := 1; i < n; i++ {
arr[i] = pref[i] ^ pref[i-1]
}
return arr
}
Ta có thể tối ưu bộ nhớ bằng cách dùng pref
để lưu kết quả luôn bằng cách loop ngược từ n-1
về 0
. Các bạn thử tự cài đặt xem như thế nào nhé. /ᐠ - ˕ -マ Ⳋ