পাইথনে পূর্ণসংখ্যার প্রতিটি সংখ্যার সাথে XOR যখন ন্যূনতম যোগফল দেয় এমন একটি সংখ্যা খুঁজুন

ধরুন আমাদের একটি অ্যারে A আছে, আমাদের একটি সংখ্যা X খুঁজে বের করতে হবে যেমন (A[0] XOR X) + (A[1] XOR X) + … + A[n – 1] XOR X যতটা সম্ভব সর্বনিম্ন।

সুতরাং, যদি ইনপুটটি [3, 4, 5, 6, 7] এর মত হয়, তাহলে আউটপুট হবে X =7 , যোগফল =10

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন search_res()। এটি arr, n
লাগবে
• উপাদান :=arr[0]
• আমি রেঞ্জ 0 থেকে arr এর আকারের জন্য, কর
  • যদি arr[i]> উপাদান, তাহলে
    • উপাদান :=arr[i]
• p :=পূর্ণসংখ্যা (এলিমেন্ট বেস 2 এর লগ) + 1
• X :=0
• আমি 0 থেকে p রেঞ্জের জন্য, কর
  • cnt :=0
  0 থেকে n রেঞ্জের মধ্যে j-এর জন্য
  • করুন
    • যদি arr[j] AND (2^i) অ-শূন্য হয়, তাহলে
      • cnt :=cnt + 1
  • যদি cnt> (n / 2) এর পূর্ণসংখ্যার অংশ অ-শূন্য হয়, তাহলে
    • X :=X + (2^i)
• সমষ্টি :=0
• আমি 0 থেকে n রেঞ্জের জন্য, কর
  • সমষ্টি :=যোগফল +(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