Pythonで要素の合計が2の累乗になるインデックスペアの数を数えるプログラム

問題の概要

数値のリスト nums が与えられたとします。このとき、i < j を満たすインデックスのペア (i, j) のうち、nums[i] + nums[j] が 2 の累乗（2^k、k ≥ 0）と等しくなるものの個数を求めます。

例えば、入力が nums = [1, 2, 6, 3, 5] の場合、出力は 3 になります。これは、合計が 2 の累乗となるペアが次の 3 つ存在するためです。

• (2, 6)：合計は 8
• (3, 5)：合計は 8
• (1, 3)：合計は 4

解決のためのアプローチ

この問題を効率よく解くために、以下の手順に従います。

• 結果を格納する変数 res を 0 で初期化します。
• 各要素の出現回数を記録するマップ（Counter）c を用意します。
• リスト内の各要素 x について、次の処理を行います。
  • j を 0 から 31 まで動かし、res に c[2^j − x] の値を加算します。つまり、それまでに登場した要素の中に「2^j − x」に一致する値がいくつあるかを調べます。
  • その後、現在の要素 x の出現回数 c[x] を 1 増やします。
• 最後に res を返します。

この手法では、各要素に対して 32 通りの累乗候補（十分に大きな範囲をカバー）をチェックするだけでよいため、全体の計算量は O(n × 32)、すなわち O(n) となります。すべてのペアを総当たりで確認する O(n²) のアプローチよりも大幅に効率的です。

実装例

理解を深めるために、実際のコードを見てみましょう。

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