ค้นหาตัวเลขที่ให้ผลรวมขั้นต่ำเมื่อ XOR กับทุกจำนวนอาร์เรย์ของจำนวนเต็มใน Python

สมมติว่าเรามีอาร์เรย์ A เราต้องหาตัวเลข X ที่ (A[0] XOR X) + (A[1] XOR X) + … + A[n – 1] XOR X มีค่าน้อยที่สุด

ดังนั้น หากอินพุตเป็นแบบ [3, 4, 5, 6, 7] ผลลัพธ์จะเป็น X =7 , Sum =10

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน search_res() นี่จะใช้เวลา arr, n
• องค์ประกอบ :=arr[0]
• สำหรับฉันในช่วง 0 ถึงขนาดของ arr ทำ
  • ถ้า arr[i]> องค์ประกอบ แล้ว
    • องค์ประกอบ :=arr[i]
• p :=จำนวนเต็มของ (ล็อกขององค์ประกอบฐาน 2) + 1
• X :=0
• สำหรับ i ในช่วง 0 ถึง p ให้ทำ
  • cnt :=0
  • สำหรับ j ในช่วง 0 ถึง n ทำ
    • ถ้า arr[j] AND (2^i) ไม่ใช่ศูนย์ ดังนั้น
      • cnt :=cnt + 1
  • ถ้า cnt> ส่วนจำนวนเต็มของ (n / 2) ไม่ใช่ศูนย์ ดังนั้น
    • X :=X + (2^i)
• ผลรวม :=0
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • sum :=sum +(X XOR arr[i])
• คืนค่า X และผลรวม

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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)

อินพุต

[3, 4, 5, 6, 7]

ผลลัพธ์

X = 7 , Sum = 10