পাইথনে তৈরি করা তালিকা থেকে নির্দিষ্ট উপাদানগুলির XOR মানগুলি খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি তালিকা দেওয়া হয়েছে যাতে প্রাকৃতিক সংখ্যা রয়েছে। এখন সেই তালিকা থেকে, আমরা তার বাইনারি উপস্থাপনায় পরপর দুটি 1s ধারণ করে এমন সমস্ত সংখ্যা সরিয়ে ফেলি এবং Z নামক আরেকটি তালিকা তৈরি করি। এখন আমাদের আরেকটি তালিকা 'ইনপুট_লিস্ট' দেওয়া হল যাতে কিছু পূর্ণসংখ্যার মান রয়েছে। আমাদের Z থেকে নির্দিষ্ট উপাদানগুলির XOR মান খুঁজে বের করতে হবে যার সূচীগুলি input_list এ নির্দিষ্ট করা আছে৷

সুতরাং, যদি ইনপুটটি input_list =[3, 4, 5] এর মত হয়, তাহলে আউটপুট হবে 9।

Z-এর 3, 4, এবং 5 সূচকে; মান হল 4, 5, এবং 8। সুতরাং, 4 XOR 5 XOR 8 =9।

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

• একটি ফাংশন zeck_num() সংজ্ঞায়িত করুন। এটি k, f_list
  লাগবে
  • res :=0
  • আমি পরিসরে (f_list -1-এর মাপ) থেকে -1, 1 দ্বারা হ্রাস করুন, করুন
    • যদি k>=f_list[i], তারপর
      • res :=res + 2^i
      • k :=k - f_list[i]
  • রিটার্ন রিটার্ন
• MOD :=10^9 + 7
• max_val :=10^18
• f_list :=1 এবং 2 মান সম্বলিত একটি নতুন তালিকা
• যখন f_list এর শেষ উপাদান <=max_val, do
  • f_list-এর শেষ উপাদান + f_list-এর শেষে f_list-এর দ্বিতীয় শেষ উপাদান যোগ করুন
• res :=0
• ইনপুট_লিস্টে প্রতিটি সূচকের জন্য, করুন
  • res :=res XOR zeck_num(index, f_list)
• Return res mod MOD

উদাহরণ

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

def zeck_num(k, f_list):
   res = 0
   for i in range(len(f_list)-1,-1,-1):
      if k >= f_list[i]:
         res += 2**i
         k -= f_list[i]
   return res

def solve(input_list):
   MOD = 10**9+7
   max_val = 10**18
   f_list = [1,2]
   while f_list[-1] <= max_val:
      f_list.append(f_list[-1] + f_list[-2])
   res = 0
   for index in input_list:
      res ^= zeck_num(index, f_list)
   return res % MOD

print(solve([3, 4, 5]))

ইনপুট

[3, 4, 5]

আউটপুট

9