Tìm số X cho tổng XOR tối thiểu với mảng trong Python

Cho mảng A, tìm số X sao cho tổng (A[0] XOR X) + ... + (A[n-1] XOR X) nhỏ nhất.

Ví dụ: [3,4,5,6,7] → X=7, Sum=10.

Thuật toán

• Tìm phần tử lớn nhất, xác định số bit p
• Với mỗi bit i từ 0 đến p-1:
  • Đếm cnt = số phần tử có bit i = 1
  • Nếu n/2: đặt bit i của X = 1
• Tính tổng XOR với X tìm được

Ví dụ mã Python

from math import log2
def search_res(arr, n):
    element = arr[0]
    for i in range(len(arr)):
        if arr[i] > element:
            element = arr[i]
    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 > int(n / 2):
            X += 1 << i
    sum = 0
    for i in range(n):
        sum += (X ^ arr[i])
    print("X =", X, ", Sum =", sum)

arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

Đầu vào

[3, 4, 5, 6, 7]

Đầu ra

X = 7 , Sum = 10