পাইথন প্রোগ্রাম - যেসব ইন্ডেক্স পেয়ারের যোগফল ২-এর ঘাত, তাদের গণনা করুন

মনে করুন nums নামে একটি সংখ্যার লিস্ট আছে। আমাদের i, j ইন্ডেক্স পেয়ারের সংখ্যা বের করতে হবে যেখানে i < j এবং nums[i] + nums[j] = 2^k কিছু 0 ≤ k-এর জন্য।

ইনপুট nums = [1, 2, 6, 3, 5] হলে আউটপুট হবে ৩, কারণ তিনটি পেয়ারের যোগফল: (6, 2): যোগফল ৮, (5, 3): যোগফল ৮ এবং (1, 3) যোগফল ৪।

সমাধানের ধাপসমূহ:

res := 0
c := nums-এ উপস্থিত প্রতিটি উপাদানের ফ্রিকোয়েন্সি ধারণকারী ম্যাপ
nums-এ প্রতিটি x-এর জন্য:
- j = 0 থেকে 31 পর্যন্ত লুপ:
  - res := res + c[(2^j) - x]
- c[x] := c[x] + 1
res ফেরত দিন

উদাহরণ

বাস্তবায়ন:

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]