Pythonで配列内の「素敵なペア」を数えるプログラムの解説

問題概要

非負の整数からなる配列 nums が与えられたとき、その中に含まれる「素敵なペア(nice pairs)」の個数を求めます。答えが非常に大きくなる可能性があるため、10^9+7 で割った余りを返します。

インデックスのペア (i, j) が「素敵なペア」とみなされるのは、以下の条件をすべて満たす場合です。

1. 0 <= i < j < nums のサイズ
2. nums[i] + rev(nums[j]) が nums[j] + rev(nums[i]) と等しい

注意: rev() は整数の正の部分のみを反転します。たとえば rev(564) は 465 を返しますが、rev(540) の場合は末尾の 0 が無視され、45 を返します。

入力が nums = [97,2,42,11] の場合、出力は 2 になります。これは、(0,2) と (1,3) の2つのペアが条件を満たすためです。1つ目のペアでは 97 + rev(42) = 97 + 24 = 121、42 + rev(97) = 42 + 79 = 121 となり、2つ目のペアでは 2 + rev(11) = 2 + 11 = 13、11 + rev(2) = 13 となり、それぞれ等しい値になっています。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• m := (10^9)+7 とする
• デフォルト値が 0 の空のマップ dic を用意する
• nums 内の各 num について:
  • rev := num を反転した値
  • dic[num - rev] を 1 増やす
• res := 0 とする
• dic のすべての値 val について:
  • res := res + (val × (val−1)) ÷ 2 の商
• res mod m を返す

アルゴリズムのポイント

この解法の鍵は、ペアの条件式を変形することにあります。「nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])」は、「nums[i] − rev(nums[i]) == nums[j] − rev(nums[j])」と書き換えられます。つまり、「num − rev(num)」の値が同じ要素同士は必ずペアを組めることになります。各キーごとの出現回数をカウントし、n 個の要素から2つ選ぶ組み合わせの数 nC2 = n×(n−1)/2 を合計すれば、答えが効率よく求まります。計算量は O(N) となり、全ペアを総当たりする O(N²) よりも大幅に高速です。

実装例

以下の Python コードで実際の動作を確認できます。

from collections import defaultdict

def solve(nums):
   m = (10**9)+7
   dic = defaultdict(int)
   for num in nums:
      rev = int(str(num)[::-1])
      dic[num-rev] += 1

   res = 0
   for val in dic.values():
      res += (val*(val-1)) // 2

   return res % m

nums = [97,2,42,11]
print(solve(nums))

入力

[97,2,42,11]

出力

2