एक संख्या खोजें जो न्यूनतम योग देता है जब पायथन में पूर्णांक की हर संख्या के साथ XOR होता है

मान लीजिए कि हमारे पास एक एरे ए है, हमें एक संख्या एक्स ढूंढनी है जैसे कि (ए [0] एक्सओआर एक्स) + (ए [1] एक्सओआर एक्स) + … + ए [एन – 1] एक्सओआर एक्स जितना संभव हो उतना न्यूनतम है।

इसलिए, यदि इनपुट [3, 4, 5, 6, 7] जैसा है, तो आउटपुट एक्स =7, योग =10 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें search_res() । इसमें गिरफ्तारी होगी, n
• तत्व:=गिरफ्तारी[0]
• मैं के लिए 0 से लेकर गिरफ्तारी के आकार तक, करते हैं
  • अगर गिरफ्तारी [i]> तत्व, तो
    • तत्व:=गिरफ्तारी[i]
• p :=का पूर्णांक (तत्व आधार 2 का लघुगणक) + 1
• X :=0
• 0 से p की श्रेणी में i के लिए, करें
  • सीएनटी:=0
  • जे के लिए 0 से n की सीमा में, करें
    • अगर arr[j] AND (2^i) शून्य नहीं है, तो
      • सीएनटी:=सीएनटी + 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