C++で配列の積に含まれる末尾のゼロの個数を数える方法

問題の概要

正の整数からなるサイズNの配列 Arr[] が与えられます。この配列のすべての要素を掛け合わせた積に含まれる、末尾のゼロ（後続ゼロ）の個数を求めるのが目標です。

解法のポイント：2と5の因数を数える

この問題は、各数値に含まれる因数を数えることで解けます。2と5の積は10であり、10が1つの末尾ゼロを生み出すため、各要素を素因数分解したときの「2の個数」と「5の個数」をカウントします。そして最終的に、数の少ない方のカウントが積の末尾ゼロの個数となります。

例えば、2が4個、5が6個ある場合、積の末尾ゼロは4個になります。2×2×2×2×5×5×5×5×5×5 = 250,000 となり、末尾にはゼロが4個並ぶからです。

具体例で確認してみましょう。

例1

入力

Arr[] = { 2, 5, 10, 15, 20, 25, 100 }

出力

末尾のゼロの個数 : 6

説明

各要素の2と5の因数（累計）:
Arr[0] = 2 = 2^1        → twos=1, fives=0
Arr[1] = 5 = 5^1        → twos=1, fives=1
Arr[2] = 10 = 2×5       → twos=2, fives=2
Arr[3] = 15 = 3×5       → twos=2, fives=3
Arr[4] = 20 = 2^2×5     → twos=4, fives=4
Arr[5] = 25 = 5^2       → twos=4, fives=6
Arr[6] = 100 = 2^2×5^2  → twos=6, fives=8
2の個数(6)が5の個数(8)より少ないため、末尾のゼロは6個となります。

例2

入力

Arr[] = { 10, 10, 10, 10, 10 }

出力

末尾のゼロの個数 : 5

説明

各要素の2と5の因数（累計）:
Arr[0] = 10 = 2×5 → twos=1, fives=1
Arr[1] = 10 = 2×5 → twos=2, fives=2
Arr[2] = 10 = 2×5 → twos=3, fives=3
Arr[3] = 10 = 2×5 → twos=4, fives=4
Arr[4] = 10 = 2×5 → twos=5, fives=5
2と5の個数が等しいため、末尾のゼロは5個となります。

アルゴリズムの手順

• 長さNの正の整数配列を受け取ります。

• 関数 trailZeros(int arr[], int n) は、配列とそのサイズnを引数に取り、全要素の積に含まれる末尾ゼロの個数を返します。

• 末尾ゼロの個数を格納する変数 count を0で初期化します。

• 2の因数の個数を格納する twos、5の因数の個数を格納する fives の2つの変数を用意します。

• forループで配列を走査します。

• 各要素について、2または5で割り切れる間、twos または fives をインクリメントし、要素を2または5で割っていきます。

• ループ終了後、twos と fives の値を比較し、小さい方を求めます。

• count に小さい方の値を代入します。

• count を結果として返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int trailZeros(int arr[], int n){
    int count = 0;
    int twos = 0;
    int fives = 0;
    for (int i = 0; i < n; i++){
        while(arr[i]%2==0 || arr[i]%5==0){
            if(arr[i]%2==0){
                arr[i]=arr[i]/2;
                twos++;
            }
            if(arr[i]%5==0){
                arr[i]=arr[i]/5;
                fives++;
            }
        }
    }
    count = twos<fives ? twos : fives;
    return count;
}
int main(){
    int Arr[]={ 12, 5, 15, 8, 100, 40 };
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << endl << "末尾のゼロの個数 : " << trailZeros(Arr, Length);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

末尾のゼロの個数 : 5

計算量について

このアルゴリズムは各要素を2と5で割り切れる限り割り続けるため、時間計算量は配列の要素数Nと各要素の因数の個数に依存し、全体として O(N log max(Arr[i])) 程度になります。また、追加の配列などを必要としないため、空間計算量は O(1) と非常に効率的です。