সূচক জোড়া গণনা করার প্রোগ্রাম যার উপাদানগুলির যোগফল পাইথনে 2 এর শক্তি

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। আমাদেরকে i, j সূচক জোড়ার সংখ্যা খুঁজে বের করতে হবে, যেখানে i =k এর জন্য 2^k এর সমান।

সুতরাং, যদি ইনপুটটি nums =[1, 2, 6, 3, 5] এর মত হয়, তাহলে আউটপুট হবে 3, যেহেতু তিনটি জোড়া যোগফল (6, 2):যোগফল 8, (5, 3) :যোগফল হল 8 এবং (1, 3) যোগফল হল 4

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

• res :=0

• c :=একটি মানচিত্র যেখানে উপস্থিত প্রতিটি উপাদানের ফ্রিকোয়েন্সি রয়েছে

• প্রতিটি x সংখ্যায়, করুন

  • 0 থেকে 31 রেঞ্জে j এর জন্য, করুন

    • res :=res + c[(2^j) - x]

  • c[x] :=c[x] + 1

• রিটার্ন রিটার্ন

উদাহরণ

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

from collections import Counter
def solve(nums):
   res, c = 0, Counter()
   for x in nums:
      for j in range(32):
         res += c[(1 << j) - x]
      c[x] += 1
   return res

nums = [1, 2, 6, 3, 5]
print(solve(nums))

ইনপুট

[1, 2, 6, 3, 5]

আউটপুট

3