algorithms/阶乘的后缀0问题

Leetcode、172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.

class Solution {
    /**
    * 125! : 125 /5 = 25 , 25 / 5 = 5, 5 /5 = 1, tot = 25 + 5 + 1 = 31,
    * 其中每个数如 15 必然有一个小于15大于10的数使得 15 * 12 或者15*14使得最后都结果中必然包含一个0
    * 
    * 此外，对于25这种数可以拆为 5 * 5，可以生成两个后缀0，因为 需要125 / 25 = 5，有5个25因子所以还要额外的加5
    *
    * 此外，对于125 这种数字可以拆为 5 * 5 * 5，这种可以生成3个后缀0，但是前面已经加了两次，所以还需要一次。即最     * 后的一个1
    */
    public int trailingZeroes(int n) {
        int res = 0;
       while(n > 0){
           res += n / 5;
           n = n / 5;
       }
        return res;
    }
}