Pythonで配列の全要素の積の符号を判定するプログラム

nums という整数型の配列があるとします。この課題では、配列に含まれるすべての要素を掛け合わせた結果の符号を求める必要があります。

例えば、入力が nums = [-2,3,6,-9,2,-4] の場合、すべての要素の積は -2592 になるため、出力は「Negative（負）」となります。

解決のアプローチ

この問題は、実際にすべての要素を掛け合わせなくても解くことができます。次の手順に従います。

• ゼロの個数を数える変数 zeroes と、負の数の個数を数える変数 negatives をそれぞれ 0 で初期化します。
• 配列 nums の各要素 i に対して、以下の処理を行います。
  • i が 0 と等しい場合、zeroes を 1 増やします。
  • i が負の数の場合、negatives を 1 増やします。
• ループ終了後、zeroes が 0 より大きければ「Zero」を返します。
• そうでなく、negatives を 2 で割った余りが 0（負の数が偶数個）であれば「Positive」を返します。
• それ以外の場合は「Negative」を返します。

この方法が成り立つのは、負の数同士を掛け合わせると正になるという数学的な性質によるものです。つまり、負の数が偶数個含まれていれば積は正になり、奇数個であれば負になります。また、要素に一つでも 0 が含まれていれば、積は必ず 0 になります。

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(nums):
   zeroes, negatives = 0, 0
   for i in nums:
      if i == 0:
         zeroes += 1
      if i < 0:
         negatives += 1
   if zeroes > 0:
      return "Zero"
   elif negatives % 2 == 0:
      return "Positive"
   else:
      return "Negative"

nums = [-2,3,6,-9,2,-4]
print(solve(nums))

入力

[-2,3,6,-9,2,-4]

出力

Negative

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、追加のメモリは定数領域（O(1)）しか使わないため、非常に大きな配列でも高速かつ効率的に動作します。