Chương trình tìm giá trị XOR tối đa cho mỗi truy vấn trong Python

Mô tả bài toán

Cho một mảng đã được sắp xếp trước nums kích thước n và một giá trị m. Chúng ta cần thực hiện truy vấn n lần như sau:

• Tìm giá trị không âm k < 2^m sao cho XOR của tất cả các phần tử trong nums và k được tối đa hóa. Giá trị k này là câu trả lời cho truy vấn thứ i.
• Loại bỏ phần tử cuối cùng khỏi mảng nums hiện tại.
• Tìm mảng answer trong đó answer[i] là câu trả lời cho truy vấn thứ i.

Ví dụ

Nếu đầu vào là nums = [0,1,1,3], m = 2, thì đầu ra sẽ là [0,3,2,3], vì:

• nums = [0,1,1,3], k = 0 vì 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
• nums = [0,1,1], k = 3 vì 0 XOR 1 XOR 1 XOR 3 = 3.
• nums = [0,1], k = 2 vì 0 XOR 1 XOR 2 = 3.
• nums = [0], k = 3 vì 0 XOR 3 = 3.

Giải thuật

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

1. Khởi tạo x := 2^m - 1.
2. Duyệt qua mảng nums từ chỉ số 0 đến n-1:
   • Cập nhật nums[i] := nums[i] XOR x.
   • Cập nhật x := nums[i].
3. Trả về mảng nums sau khi đảo ngược.

Triển khai Python

def solve(nums, m):
    x = 2**m - 1
    for i in range(len(nums)):
        nums[i] ^= x
        x = nums[i]
    return nums[::-1]

nums = [0, 1, 1, 3]
m = 2
print(solve(nums, m))

Đầu vào

[0,1,1,3], 2

Đầu ra

[0, 3, 2, 3]