Tìm một số cho tổng tối thiểu khi XOR với mọi số mảng số nguyên trong Python

Giả sử chúng ta có một mảng A, chúng ta phải tìm một số X sao cho (A [0] XOR X) + (A [1] XOR X) +… + A [n - 1] XOR X là nhỏ nhất có thể.

Vì vậy, nếu đầu vào là [3, 4, 5, 6, 7], thì đầu ra sẽ là X =7, Sum =10

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm search_res (). Điều này sẽ mất arr, n
• phần tử:=arr [0]
• đối với tôi trong phạm vi từ 0 đến kích thước của arr, thực hiện
  • if arr [i]> phần tử, then
    • phần tử:=arr [i]
• p:=integer of (log của phần tử cơ số 2) + 1
• X:=0
• đối với tôi trong phạm vi từ 0 đến p, thực hiện
  • cnt:=0
  • đối với j trong phạm vi từ 0 đến n, thực hiện
    • nếu arr [j] AND (2 ^ i) khác 0, thì
      • cnt:=cnt + 1
  • nếu cnt> phần nguyên của (n / 2) khác 0, thì
    • X:=X + (2 ^ i)
• sum:=0
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • sum:=sum + (X XOR arr [i])
• trả về X và tổng

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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