Pythonでn個の数値の積の末尾に連続するゼロの個数を求める方法

n個の数値からなる配列が与えられたとき、それらすべてを掛け合わせた結果の末尾に、ゼロがいくつ連続して並ぶかを求める問題について解説します。

例えば、入力が [200, 20, 5, 30, 40, 14] の場合を考えてみましょう。200 × 20 × 5 × 30 × 40 × 14 = 336000000 となり、末尾には6個のゼロが続くため、出力は 6 になります。

考え方：2と5の因数を数える

積の末尾にゼロが付くのは、「2」と「5」がペアになって掛け合わされ、10の倍数が生まれた場合です。したがって、各数値に含まれる2の因数の総数と5の因数の総数をそれぞれ数え、そのうち小さい方の値が末尾のゼロの個数となります。

具体的な手順は以下の通りです。

• 関数 count_fact_two() を定義します。引数として n を受け取ります
• count := 0 と初期化します
• n を 2 で割った余りが 0 の間、次を繰り返します
  • count := count + 1
  • n := n / 2(商のみ、整数除算)
• count を返します
• 同様に関数 count_fact_five() を定義します。2ではなく5で割り続ける点だけが異なります
• メイン処理では以下を実行します
• n := 配列 A のサイズ
• twos := 0、fives := 0 と初期化します
• i を 0 から n-1 まで繰り返します
  • twos := twos + count_fact_two(A[i])
  • fives := fives + count_fact_five(A[i])
• twos と fives のうち小さい方の値を返します(これが末尾のゼロの個数です)

なぜ小さい方を返すのか?

10 = 2 × 5 であるため、末尾のゼロ1個は「2と5のペア」1組に対応します。どちらか一方が不足するとペアを作れないため、2の因数と5の因数のうち少ない方の数が、作れる10の個数、すなわち末尾のゼロの個数になります。上記の例では、全体に含まれる5の因数が6個であるため、答えは6となります。

実装例

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

def count_fact_two(n):
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    return count

def count_fact_five(n):
    count = 0
    while n % 5 == 0:
        count += 1
        n = n // 5
    return count

def get_consecutive_zeros(A):
    n = len(A)
    twos = 0
    fives = 0
    for i in range(n):
        twos += count_fact_two(A[i])
        fives += count_fact_five(A[i])
    if twos < fives:
        return twos
    else:
        return fives

A = [200, 20, 5, 30, 40, 14]
print(get_consecutive_zeros(A))

入力

[200, 20, 5, 30, 40, 14]

出力

6

計算量について

このアルゴリズムは、各要素に対して2または5で割り切れなくなるまで除算を繰り返すため、時間計算量は配列の長さを n、最大値を M とすると O(n log M) 程度になります。実際に巨大な積を計算する必要がないため、数値が非常に大きくなる場合でも効率的に動作するのが大きな利点です。