पायथन में ऐरे से एलिमेंट के साथ अधिकतम XOR खोजने का प्रोग्राम

मान लीजिए हमारे पास नॉन-नेगेटिव मानों वाला nums नामक एक ऐरे है। हमारे पास queries नामक एक और ऐरे है जहां queries[i] में एक जोड़ी (xi, mi) होती है। i-वीं क्वेरी का उत्तर xi और nums के किसी भी एलिमेंट का अधिकतम बिटवाइज XOR मान है जो mi से कम या बराबर है। यदि nums में सभी एलिमेंट mi से बड़े हैं, तो उत्तर -1 है। तो हमें एक ऐरे answer ढूंढना है जहां answer का आकार query के आकार के बराबर हो और answer[i] i-वीं क्वेरी का उत्तर हो।

उदाहरण के लिए, यदि इनपुट nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] है, तो आउटपुट [3,3,7] होगा, क्योंकि:

• 0 और 1, 10 XOR 3 = 3 और 1 XOR 3 = 2, यहां इनमें से बड़ा 3 है।
• 1 XOR 2 = 3।
• 5 XOR 2 = 7।

हल करने के चरण

1. m := len(nums)
2. n := len(queries)
3. queries = प्रत्येक इंडेक्स i और जोड़ी (x, limit) के लिए ट्रिपलेट (i, x, limit) बनाएं
4. queries को limit के आधार पर सॉर्ट करें
5. nums := nums सूची को सॉर्ट करें
6. res := आकार n का ऐरे और 0 से भरें
7. k को 31 से 0 तक घटाते हुए लूप चलाएं:
   • prefixes := एक नया सेट
   • j := 0
   • queries में प्रत्येक इंडेक्स i और मान (x, limit) के लिए:
     • j <= m - 1 और nums[j] <= limit तक व्हाइल लूप चलाएं:
       • nums[j] को दाईं ओर k बिट शिफ्ट करें और prefixes में डालें
       • j := j + 1
     • यदि prefixes खाली है, तो res[i] := -1
     • अन्यथा:
       • res[i] <<= 1
       • target := res[i] XOR 1
       • यदि (x >> k) XOR target prefixes में है, तो res[i] := target
8. res वापस करें।

उदाहरण

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

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]