172. 阶乘后的零

题意：

解题思路：

/*
    求n!
    0的来源 2 * 5 所以一对2和5即可产生一个0,所以0的个数即为min(阶乘中5的个数和2的个数) 
    又因为是2的倍数的数一定比是5的倍数的数多 所以2的个数一定>=5的个数 所以只需要统计 5 的个数了
    例如 5！ = 1 * 2 * 3 * 4 * 5
                  2      2 2  5    一个2和一个5配对出现0 所以5!末尾只有一个零
        而在 n = 25 时 可以产生5的有 5 10 15 20 25 
                   即 n/5 = 5个 然鹅 25 = 5*5 所以少算了一个5 
        n>=25时,故而需要补上它 因此所有可以产生25的也要加上 
                   即为 n/5 + n/25  然鹅 125 = 5*25 所以又少算了一个5
        n>=125时,故而需要补上它 因此所有可以产生125的也要加上
                   即为 n/5 + n/25 + n/125  然鹅 625 = 5*125 所以又少算了一个5
        继续补上...
        所以最终为 n/5 + n/25 + n/125 + n/625 + ... 
                即 n/5 + n/5/5 + n/5/5/5 + n/5/5/5/5 + ... 
        代码如下:
    */

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    // Time: O(log_5(n)), Space: O(1)
    function trailingZeroes($n) {
        $cnt = 0;
        //$n >= 5
        while ($n > 0) {
            $n = floor($n/5);
            $cnt += $n;
        }
        return $cnt;
    }
    function trailingZeroes($n) {
        if ($n == 0) return 0;
        return floor($n / 5) + $this->trailingZeroes($n / 5);
    }
}

go代码实现：

func trailingZeroes(n int) int {
    res := 0
    for n > 0 {//n >= 5
        res += n / 5
        n /= 5
    }
    return res
}