Pythonで配列に「他の要素の積と等しい値の要素」が存在するか判定する方法

「nums」という配列が与えられたとき、その配列の中に「それ以外のすべての要素の積と等しい値を持つ要素」が存在するかどうかを判定する問題を考えてみましょう。

たとえば、入力が nums = [3,2,24,4,1] の場合、出力は True になります。これは、24 = 3 × 2 × 4 × 1 となり、要素 24 が他のすべての要素の積とちょうど一致しているためです。

解決のアプローチ

この問題は、次の手順で解くことができます。

• 変数 mul を 1 で初期化します。
• 配列のすべての要素を掛け合わせて、全体の積 mul を求めます。
• 再度配列を走査し、各要素 nums[i] が mul / nums[i](自分自身を除いた残りの要素の積)と一致するかどうかを確認します。
• 一致する要素が見つかれば True を返し、最後まで見つからなければ False を返します。

以下の実装例を見ると、より理解しやすくなります。

実装コード

def solve(nums):
   mul = 1
   for i in range(len(nums)):
      mul *= nums[i]
 
   for i in range(len(nums)):
      if nums[i] == mul / nums[i]:
         return True
 
   return False
 
nums = [3,2,24,4,1]
print(solve(nums))

入力

[3,2,24,4,1]

出力

True

計算量と注意点

このアルゴリズムは配列を2回走査するだけで済むため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。ただし、浮動小数点の除算では丸め誤差が生じる可能性があるため、厳密な判定が必要な場合は、「nums[i] == mul / nums[i]」を「mul == nums[i] * nums[i]」という乗算による比較に置き換えると安全です。この形に書き換えても数学的には同じ条件を表しており、整数演算のみで正確に判定できます。