ปัญหา
อาร์เรย์ nums และค่า k XOR ของ Segment [left, right] = XOR ของ Element ทุกตัวในช่วง หาจำนวน Element น้อยที่สุดที่ต้องเปลี่ยน ให้ XOR ของทุก Segment ขนาด k = 0
ตัวอย่าง
nums = [3,4,5,2,1,7,3,4,7], k = 3 → Output: 3
แก้: เปลี่ยน Index 2,3,4 → [3,4,7,3,4,7,3,4,7] ทุก Segment ขนาด 3 XOR = 0
อัลกอริทึม (DP on XOR Values per Position Mod k)
- กลุ่ม Element ตาม Index mod k → k Groups
- แต่ละ Group ต้องมีค่าเดียวกันทั้งหมด (เพื่อ XOR Segment = 0)
- DP: dp[x] = จำนวน Element ที่เก็บได้มากที่สุด ถ้า XOR ของค่าที่เลือก = x
- สำหรับแต่ละ Group: ลองเลือกค่า v ที่มีใน Group → New DP[x XOR v] = Max(DP[x] + Count[v])
- คำตอบ = n - dp[0]
ตัวอย่างโค้ด
def solve(nums, k):
LIMIT = 2**10 # 1024
temp = [[0 for _ in range(LIMIT)] for _ in range(k)]
for i, x in enumerate(nums):
temp[i % k][x] += 1
dp = [-2000 for _ in range(LIMIT)]
dp[0] = 0
for row in temp:
maxprev = max(dp)
new_dp = [maxprev for _ in range(LIMIT)]
for i, cnt in enumerate(row):
if cnt > 0:
for j, prev in enumerate(dp):
new_dp[i ^ j] = max(new_dp[i ^ j], prev + cnt)
dp = new_dp
return len(nums) - dp[0]
nums = [3,4,5,2,1,7,3,4,7]
k = 3
print(solve(nums, k)) # Expected: 3 (Note: Example output shows -9, likely bug in original)หมายเหตุ
ตัวอย่าง Output ในต้นฉบับแสดง -9 ซึ่งไม่ถูกต้อง (ควรเป็น 3) โค้ดข้างต้นแก้ไข Logic ให้ถูกต้อง
ความซับซ้อน
- Time: O(k × LIMIT²) ≈ O(k × 1024²)
- Space: O(LIMIT)
