पायथन में सरणी से एक तत्व के साथ अधिकतम XOR खोजने का कार्यक्रम

मान लीजिए कि हमारे पास गैर-ऋणात्मक मानों के साथ nums नामक एक सरणी है। हमारे पास क्वेरीज़ नामक एक अन्य सरणी भी है जहां क्वेरीज़ [i] की एक जोड़ी (xi, mi) है। ith क्वेरी का उत्तर xi का अधिकतम बिटवाइज़ XOR मान है और अंकों का कोई भी तत्व जो mi से कम या उसके बराबर है। यदि अंकों में सभी तत्व मील से बड़े हैं, तो उत्तर -1 है। इसलिए हमें एक सरणी उत्तर खोजना होगा जहां आकार का उत्तर क्वेरी के आकार के समान हो और उत्तर [i] ith क्वेरी का उत्तर हो।

इसलिए, यदि इनपुट अंकों की तरह है =[0,1,2,3,4] प्रश्न =[[3,1], [1,3], [5,6]], तो आउटपुट [3, 3,7], क्योंकि

• 0 और 1 1 से बड़े नहीं हैं। 0 XOR 3 =3 और 1 XOR 3 =2, यहाँ इन दोनों में से बड़ा 3 है।

• 1 एक्सओआर 2 =3.

• 5 एक्सओआर 2 =7.

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

• मी :=अंकों का आकार

• n :=प्रश्नों का आकार

• query =प्रत्येक अनुक्रमणिका i के लिए एक त्रिक (i, x, सीमा) बनाएं, और प्रश्नों में जोड़ी (x, सीमा) बनाएं

• सीमा के आधार पर प्रश्नों को क्रमबद्ध करें

• अंक :=सूची संख्या क्रमित करें

• res :=आकार n की एक सरणी और 0 से भरें

• के लिए 31 से 0 की सीमा में, 1 से घटाएं, करें

  • उपसर्ग :=एक नया सेट

  • जे:=0

  • प्रश्नों में प्रत्येक अनुक्रमणिका i और मान (x, सीमा) के लिए, करें

    • जबकि j <=m - 1 और nums[j] <=सीमा, करें

      • nums[j] को दाएँ k बिट्स में शिफ्ट करें और प्रीफ़िक्स में डालें

      • जे:=जे + 1

    • अगर उपसर्ग खाली है, तो

      • रेस [i] :=-1

    • अन्यथा,

      • रेस [i] =रेस का भाग [i]/2

      • लक्ष्य:=रेस [i] एक्सओआर 1

      • अगर (x k बिट्स को दाईं ओर स्थानांतरित करने के बाद) XOR लक्ष्य उपसर्गों में है, तो

        • रेस [i] :=लक्ष्य

• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

def solve(nums, queries):
   m, n = len(nums), len(queries)
   queries = sorted(((i, x, limit) for i, (x, limit) in
enumerate(queries)), key=lambda x: x[2])
   nums = sorted(nums)
   res = [0] * n
   for k in range(31, -1, -1):
      prefixes = set()
      j = 0
      for i, x, limit in queries:
         while j <= m - 1 and nums[j] <= limit:
            prefixes.add(nums[j] >> k)
            j += 1
         if not prefixes:
            res[i] = -1
         else:
            res[i] <<= 1
            target = res[i] ^ 1
            if (x >> k) ^ target in prefixes:
               res[i] = target
   return res

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))

इनपुट

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

आउटपुट

[3, 3, 7]