読者です 読者をやめる 読者になる 読者になる

階乗のゼロ Cracking the Coding the Interview

問題

整数Nが与えら、Nの階乗を計算した時に、末尾に連なる0の数を求める問題。

解き方

どんな時に末尾に0が来るか考える。階乗の計算では足し算はなく掛け算のみなので、10を掛けた時に末尾に0がつく。また、10は2×5なので2と5を掛けた回数分、0が着くことが分る。また、5を掛ける回数は2を掛ける回数に比べ多いので、5を掛ける回数を数えれば良い。


N = 10の時
階乗は1×2×3×4×5×6×7×8×9×10

上記で5を掛けているのは2回(5, 10)なので末尾には0が2つ着く。これはN / 5で求められる。また、25を掛けた場合を考えると、5を2回掛けている事が分る。よってコードは以下のようになる。