Chương trình khôi phục mảng bị mã hóa XOR trong Python

Giả sử ta có mảng ẩn arr với n số nguyên không âm. Mảng này được mã hóa thành mảng enc độ dài n-1 với enc[i] = arr[i] XOR arr[i+1]. Cho mảng enc và số nguyên first (phần tử đầu tiên của mảng gốc), ta phải tìm mảng gốc.

Ví dụ: enc = [8,3,2,7], first = 4, kết quả là [4, 12, 15, 13, 10].

Giải thuật

1. arr := [first]
2. For i từ 0 đến len(enc) - 1:
   • Thêm arr[i] XOR enc[i] vào cuối arr
3. Trả về arr

Ví dụ (Python)

def solve(enc, first):
    arr = [first]
    for i in range(len(enc)):
        arr.append(arr[i] ^ enc[i])
    return arr

enc = [8, 3, 2, 7]
first = 4
print(solve(enc, first))

Input

[8,3,2,7], 4

Output

[4, 12, 15, 13, 10]