ภาพรวม
โจทย์หาตัวเลข X ที่ทำให้ผลรวม (A[i] XOR X) น้อยที่สุด
ตัวอย่าง
A = [3, 4, 5, 6, 7]
X = 7 → ผลรวม = (3⊕7)+(4⊕7)+(5⊕7)+(6⊕7)+(7⊕7) = 4+3+2+1+0 = 10
หลักการ: Bitwise Majority
พิจารณาแต่ละบิตแยกกัน สำหรับบิต i:
- นับจำนวน 1 ในบิต i ของทุก A[j] → cnt
- ถ้า cnt > n/2 → ตั้งบิต i ของ X = 1 (เพื่อให้ XOR กลายเป็น 0 ส่วนใหญ่)
- ถ้า cnt ≤ n/2 → ตั้งบิต i ของ X = 0
เพราะ 1⊕1=0, 0⊕0=0, 1⊕0=1, 0⊕1=1 → ต้องการให้ XOR 0 ส่วนใหญ่
โค้ด Python
from math import log2
def search_res(arr, n):
element = max(arr)
p = int(log2(element)) + 1
X = 0
for i in range(p):
cnt = 0
for j in range(n):
if arr[j] & (1 << i):
cnt += 1
if cnt > n // 2:
X += 1 << i
total = sum(X ^ val for val in arr)
print("X =", X, ", Sum =", total)
arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)
ผลลัพธ์
X = 7 , Sum = 10
