Pythonで要素の合計が2の累乗であるインデックスペアをカウントするプログラム

numsという番号のリストがあるとします。インデックスペアの数i、jを見つける必要があります。ここで、i =kに対して2^kに等しくなるようにします。

したがって、入力がnums =[1、2、6、3、5]のようである場合、（6、2）のような3つのペアの合計があるため、出力は3になります。合計は8、（5、3） ：合計は8、（1、3）合計は4

これを解決するには、次の手順に従います-

• res：=0

• c：=に存在する各要素の頻度を含むマップ

• numsの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