2017-06-11 23:45:42 +0000   |     algorithm leetcode math   |   Viewed times   |    

题目

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

Note: Your solution should be in logarithmic time complexity.

找数学规律,复杂度

首先,trailing zeroes就是指 末尾的连续的0

其实很简单,因为能产生末尾的0的只有相乘为10的数。只有2*5=10

所以本质上 遇到一个5末尾就有一个0。因为前面的2有的是。

但这题的关键点就在于,

25   = 5^2    // 能分解出两个5
125  = 5^3    // 能分解出三个5
...
**** = 5^n    // 能分解出n个5

代码

public class Solution {
    public int trailingZeroes(int n) {
        int ret = 0;
        long fivePower = 1l;
        while (true) {
            fivePower = fivePower * 5;
            if (n >= fivePower) {
                ret += n / fivePower;
            } else {
                break;
            }
        }
        return ret;
    }
}

以下是简洁版,

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

结果

factorial-trailing-zeroes-1

递归版

递归版只有一行,你怕不怕?

代码

public class Solution {
    public int trailingZeroes(int n) {
        return (n == 0)? 0 : n / 5 + trailingZeroes(n/5);
    }
}

结果

factorial-trailing-zeroes-2