【Python】リスト内で合計が奇数になるペアの数を数えるプログラムの書き方

正の整数のリスト nums が与えられたとき、i < j を満たすインデックスの組 (i, j) のうち、nums[i] + nums[j] の合計が奇数になる「有効なペア」の数を求める問題を考えてみましょう。

例えば、入力が [5, 4, 6] の場合、出力は 2 になります。これは、[5, 4] と [5, 6] の2つのペアの合計（9 と 11）がどちらも奇数になるためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• e := リスト nums から偶数のみを取り出した新しいリストを作成する
• (nums の要素数 − e の要素数) × e の要素数 を返す

一見シンプルですが、この式には明確な理由があります。「偶数 + 奇数 = 奇数」という性質を利用すると、合計が奇数になるペアは必ず「1つの偶数と1つの奇数」の組み合わせであることが分かります。したがって、偶数の個数と奇数の個数を掛け合わせるだけで、全ての有効なペアを数え上げることができるのです。

この方法なら、全てのペアを二重ループで確認する O(n²) の手法と比べ、O(n) で高速に処理できます。

実装例

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

class Solution:
   def solve(self, nums):
      e=[i for i in nums if i%2==0]
      return (len(nums)-len(e))*len(e)
nums = [5, 4, 6]
ob = Solution()
print(ob.solve(nums))

入力

[5, 4, 6]

出力

2

コードでは、リスト内包表記を使って偶数だけを抽出し、全体の要素数から偶数の数を引くことで奇数の個数を求めています。最後に両者を掛け合わせることで、答えとなる 2 が出力されます。