【LeetCode从零单刷】Factorial Trailing Zeroes

タイトル:
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
回答:
nの階乗の末尾には何個の0がありますか.つまり、結果が10の何倍なのかを尋ねることです.10=2*5なので乗数ごとに因数分解すればよい.
そのため、私の最初の方法は各数を遍歴して、それは2の何倍で、5の何倍で、それぞれ和を求めて、sum 2とsum 5のもっと小さい値を取ります.答えは正しいが、タイムアウトした.
各数を遍歴して計算しなくてもいいですか?
まず、分解の因式の中で、2の個数は5よりはるかに多いに違いないということを確定する必要があります.したがって、10の倍数は5の因数個数に依存する.考えてみてください.

~n個の数のうち、5個毎に1つの5が生成され、これは(n/5)個の5が生成される.

は25個の数ごとに1つの5を多く生成し、これは多く(n/25)つの5を生成する.

は125個の数ごとに、また1つの5を多く生成し、これは多く(n/125)個の5を生成する.

……

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while(n > 1) {
            ans += n/5;
            n = n/5;
        }
        return ans;
    }
};