পাইথনে অ্যারে থেকে একটি উপাদান সহ সর্বাধিক XOR খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের নন-নেগেটিভ মান সহ nums নামে একটি অ্যারে আছে। আমাদের আরও একটি অ্যারে আছে যার নাম queries যেখানে queries[i] এর একটি জোড়া (xi, mi) আছে। ith কোয়েরির উত্তর হল xi-এর সর্বোচ্চ বিটওয়াইজ XOR মান এবং সংখ্যার যেকোন উপাদান যা mi এর থেকে কম বা সমান। যদি সংখ্যার সমস্ত উপাদান মাই এর থেকে বড় হয়, তবে উত্তর হবে -1। সুতরাং আমাদের একটি অ্যারে উত্তর খুঁজে বের করতে হবে যেখানে উত্তরের সাইজ কোয়েরির আকারের সমান এবং উত্তর[i] হল ith প্রশ্নের উত্তর।

সুতরাং, যদি ইনপুটটি nums =[0,1,2,3,4] queries =[[3,1],[1,3],[5,6]] এর মত হয়, তাহলে আউটপুট হবে [3, 3,7], কারণ

• 0 এবং 1 1 এর চেয়ে বড় নয়। 0 XOR 3 =3 এবং 1 XOR 3 =2, এখানে এই দুটির মধ্যে বড় হল 3।

• 1 XOR 2 =3.

• 5 XOR 2 =7.

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

• m :=সংখ্যার আকার

• n :=প্রশ্নের আকার

• প্রশ্ন =প্রতিটি সূচক i এর জন্য একটি ট্রিপলেট (i, x, সীমা) তৈরি করুন এবং প্রশ্নগুলিতে জোড়া (x, সীমা) করুন

• সীমার উপর ভিত্তি করে প্রশ্নগুলি সাজান

• সংখ্যা :=তালিকার সংখ্যাগুলি সাজান

• res :=n আকারের একটি অ্যারে এবং 0

  দিয়ে পূরণ করুন

• 31 থেকে 0 রেঞ্জের k-এর জন্য, 1 দ্বারা হ্রাস করুন, করুন

  • উপসর্গ :=একটি নতুন সেট

  • j :=0

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

    • যখন j <=m - 1 এবং nums[j] <=limit, do

      • nums[j] কে ডান k বিটে স্থানান্তর করুন এবং উপসর্গগুলিতে সন্নিবেশ করুন

      • j :=j + 1

    • যদি উপসর্গ খালি হয়, তাহলে

      • res[i] :=-1

    • অন্যথায়,

      • res[i] =res[i]/2

        এর ভাগফল

      • লক্ষ্য :=res[i] XOR 1

      • যদি (x k বিট ডানদিকে সরানোর পরে) XOR লক্ষ্য উপসর্গে থাকে, তাহলে

        • res[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]