โปรแกรมหาค่า XOR สูงสุดสำหรับแต่ละคิวรีใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียงลำดับไว้แล้วชื่อ nums ขนาด n และมีค่า m เราต้องการดำเนินการคิวรี n ครั้ง ดังนี้:

• ค้นหาค่า k ที่ไม่เป็นลบและน้อยกว่า 2^m ทำให้ค่า XOR ของทุกองค์ประกอบใน nums และ k มีค่าสูงสุด ค่า k นี้คือคำตอบของคิวรีที่ i
• นำองค์ประกอบตัวสุดท้ายออกจากอาร์เรย์ nums ปัจจุบัน
• เราต้องหาอาร์เรย์ answer โดยที่ answer[i] คือคำตอบของคิวรีที่ i

ตัวอย่างเช่น หากอินพุตคือ nums = [0,1,1,3], m = 2 ผลลัพธ์จะเป็น [0,3,2,3] เนื่องจาก:

• nums = [0,1,1,3], k = 0 เพราะ 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3
• nums = [0,1,1], k = 3 เพราะ 0 XOR 1 XOR 1 XOR 3 = 3
• nums = [0,1], k = 2 เพราะ 0 XOR 1 XOR 2 = 3
• nums = [0], k = 3 เพราะ 0 XOR 3 = 3

วิธีแก้ปัญหา

1. x := 2^m - 1
2. สำหรับ i ในช่วง 0 ถึง ขนาดของ nums - 1:
   • nums[i] := nums[i] XOR x
   • x := nums[i]
3. คืนค่า nums หลังจากกลับลำดับ

ตัวอย่างโค้ด

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))

อินพุต

[0,1,1,3], 2

เอาต์พุต

[0, 3, 2, 3]