পাইথনে সীমার চেয়ে কম এবং XOR সর্বাধিক উপাদানগুলির তালিকা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার সংখ্যার একটি তালিকা এবং প্রশ্নের একটি তালিকা রয়েছে যেখানে প্রতিটি প্রশ্নে [x, সীমা] রয়েছে। আমাদের এমন একটি তালিকা খুঁজে বের করতে হবে যাতে প্রতিটি প্রশ্নের জন্য [x, সীমা], আমরা সংখ্যায় একটি উপাদান e পাই যাতে e ≤ সীমা এবং e XOR x সর্বাধিক করা হয়। যদি এমন কোনো উপাদান না থাকে, তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি nums =[3, 5, 9] queries =[[4, 6],[2, 0]] এর মত হয়, তাহলে আউটপুট হবে [3, -1], প্রথম প্রশ্নের মতো, আমরা সংখ্যায় 2 বা 4 ব্যবহার করতে পারি। 3 ^ 4 =7 যখন 5 ^ 4 =3 তাই আমরা 3 নির্বাচন করি যা বড় XOR দেয়। দ্বিতীয় ক্যোয়ারীতে, এমন কোন সংখ্যা নেই যা 0 এর থেকে কম বা সমান, তাই আমরা এটিকে -1 এ সেট করেছি।

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

• trie :=একটি নতুন মানচিত্র

• একটি ফাংশন বিটস() সংজ্ঞায়িত করুন। এর জন্য i

  লাগবে

• i

  এর 32 বিট বাইনারি উপস্থাপনা ফেরত দিন

• একটি ফাংশন সন্নিবেশ সংজ্ঞায়িত করুন। এর জন্য i

  লাগবে

• নোড :=চেষ্টা করুন

• প্রতিটি c-এর জন্য বিট(i), করুন

  • নোড :=যদি c নোডে না থাকে তবে এর ভিতরে একটি খালি মানচিত্র ঢোকান

• নোড[2] :=i

• একটি ফাংশন ক্যোয়ারী () সংজ্ঞায়িত করুন। এর জন্য i

  লাগবে

• নোড :=চেষ্টা করুন

• প্রতিটি c-এর জন্য বিট(i), করুন

  • rc :=c XOR 1

  • নোড :=নোড[আরসি] যদি বিদ্যমান থাকে অন্যথায় নোড[সি]

• রিটার্ন নোড[2]

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• তালিকা A

  সাজান

• B :=প্রতিটি ক্যোয়ারী সূচক i এবং ক্যোয়ারী মান x এবং সীমার জন্য ফর্মের উপাদানগুলির একটি তালিকা (i, x, সীমা)। তারপর সীমার উপর ভিত্তি করে সাজান

• (j, n, ans) :=(0, A এর আকার , প্রশ্নগুলির মতো আকারের একটি তালিকা, -1 দিয়ে পূরণ করুন)

• প্রতিটি সূচকের জন্য i এবং মান x এবং B তে সীমা, করুন

  • যখন j

    • সন্নিবেশ (A[j])

    • j :=j + 1

  • যদি j অ-শূন্য হয়, তাহলে

    • উত্তর[i] :=প্রশ্ন(x)

• উত্তর ফেরত দিন

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

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]