Factorial Trailing Zeroes

    2.     # @param {integer} n
    3.     # @return {integer}
    4.         if n < 0:
    5.             return -1
    7.         count = 0
    8.         while n > 0:
    9.             n /= 5
    10.             count += n
    12.         return count

    C++

    Java

    1. public class Solution {
    3.         if (n < 0) {
    4.             return -1;
    5.         }
    7.         int count = 0;
    8.         for (; n > 0; n /= 5) {
    9.             count += (n / 5);
    10.         }
    11.         return count;
    12.     }
    13. }
    1. 异常处理，小于0的数返回-1.
    2. 先计算5的正整数幂都有哪些，不断使用 n / 5 即可知质因数5的个数。
    3. 在循环时使用 n /= 5 而不是 , 可有效防止溢出。

    复杂度分析

    可以使用迭代处理的程序往往用递归，而且往往更为优雅。递归的终止条件为n <= 0.

    Python

    1. class Solution {
    2. public:
    3.     int trailingZeroes(int n) {
    4.         if (n == 0) {
    5.             return 0;
    6.         } else if (n < 0) {
    7.             return -1;
    8.         } else {
    9.             return n / 5 + trailingZeroes(n / 5);
    10.         }
    12. };

    Java

    源码分析

    递归层数最大为 \log_5 n, 返回值均在栈上，可以认为没有使用辅助的堆空间。