पायथन में उन तत्वों की सूची ज्ञात करने का प्रोग्राम जो सीमा से कम हैं और XOR अधिकतम है

मान लीजिए हमारे पास संख्याओं की एक सूची nums और क्वेरी की एक सूची है जहां प्रत्येक क्वेरी में [x, limit] होता है। हमें एक सूची ढूंढनी है जैसे कि प्रत्येक क्वेरी [x, limit] के लिए, हम nums में एक तत्व e ढूंढें जैसे कि e <= limit और e XOR x अधिकतम हो। यदि ऐसा कोई तत्व नहीं है, तो -1 वापस करें।

उदाहरण के लिए, nums = [3,5,9], queries = [[4,6],[2,0]] के लिए आउटपुट [3, -1] होगा।

एल्गोरिदम (ट्राई + ऑफलाइन प्रोसेसिंग)

• trie := नया मैप
• bits(i) फ़ंक्शन: 32-बिट बाइनरी प्रतिनिधित्व वापस करें
• insert(i): ट्राई में डालें
• query(i): अधिकतम XOR देने वाला तत्व ढूंढें
• मुख्य विधि:
  • A को सॉर्ट करें
  • B := (index, x, limit) के रूप में क्वेरी, limit के अनुसार सॉर्ट की गई
  • j=0, n=len(A), ans=[-1]*len(queries)
  • प्रत्येक (i, x, limit) in B के लिए:
    • जब j < n और A[j] <= limit: insert(A[j]), j++
    • यदि j > 0, तो ans[i] = query(x)
  • ans वापस करें

उदाहरण

class Solution:
    def solve(self, A, queries):
        trie = {}
        def bits(i):
            return map(int, bin(i)[2:].zfill(32))
        def insert(i):
            node = trie
            for c in bits(i):
                node = node.setdefault(c, {})
            node[2] = i
        def query(i):
            node = trie
            for c in bits(i):
                rc = c ^ 1
                node = node.get(rc, node.get(c))
            return node[2]
        A.sort()
        B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
        j, n, ans = 0, len(A), [-1]*len(queries)
        for i, x, limit in B:
            while j < n and A[j] <= limit:
                insert(A[j])
                j += 1
            if j: ans[i] = query(x)
        return ans

ob = Solution()
nums = [3,5,9]
queries = [[4,6],[2,0]]
print(ob.solve(nums, queries))

इनपुट

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

आउटपुट

[3, -1]