暴力解
------------------------一些年轻的尝试,大佬可跳过---------------------------
我觉得暴力解也可以?n最大取到一万
只不过时间是线性的,不是logn
import java.math.BigInteger;
class Solution {
public int trailingZeroes(int n) {
BigInteger factorial = BigInteger.ONE; // factors start with 1
for (int i = 2; i <= n; i++) // start computing from 2 onwards
factorial = factorial.multiply(BigInteger.valueOf(i));
int count = 0;
// remember, you can't use normal arithmetic operators with BigInteger
while (factorial.mod(BigInteger.TEN) == BigInteger.ZERO) {
factorial = factorial.divide(BigInteger.TEN);
count++;
}
return count;
}
}
事实证明我还是太年轻,10^4 !已经是非常大的数了
我之前debug还用 long,之后发现当 n = 30的时候就需要导入BitInteger了
讲道理BitInteger 应该是没有上限的,为啥我n 到4575的时候就TLE了?
以及:BitInteger是个什么东东?
正文
我又来扒Y总的视频了,请叫我字幕组
推导思路
小学数奥题
首先,考虑一下一个数末尾0的个数,取决于什么
取决于这个数 可以因式分解出 多少个10
同时10 = 2 x 5,所以这个找出多少个10,也取决于 能找出多少个2 x 5
假设n!= k, 就是需要找 k里面有多少个2 x 5, 有多少个需要用幂数 表示,所以
k = 2^a x 5^b x ....
也就是 min(a,b) 对儿 个10
接下来,怎么去求 一个数里面有多少个因子2和5呢?
先考虑一个一般性的问题:一个n!里 有多少个(质)因子p?
肯定不应该去硬分解,这样时间复杂度是O(n)
怎么分解?
1. 1~n中 p的倍数,[n/p]下取整
2. 再求1~n中,p^2的个数,也下取整
3. 再来看有多少p^3
4. …以此类推,直到除到0为止
所以,n!里面 有多少个p的个数,就是所有的 [n/p^(1..n)]的和
那么接下来,回到本题继续推理,求一个数里面有多少个2 和 5
就可以把上述式子的p替换成 2 和 5,也就是
[n/2^1] + [n/2^2] + [n/2^3] + .....+ [n/2^n] ~a个
[n/5^1] + [n/5^2] + [n/5^3] + .....+ [n/5^n] ~b个
经过第一步分析,我们知道k = 2^a x 5^b x ....
取 min(a,b)个,也就是能构成min个10,也就是末位有min个0
然后又在这一步推导中发现,因为分子n不变,分母越大的数,整除之后的个数越少,所以/5的数肯定比/2的数少,所以min肯定就落在了/5的头上
所以本题,直接看n!里面有几个5就好了,就间接的代表着,这个n!末位有几个10,也就是几个0
所以本题就转化成: 求n 里面有几个5
Java代码
小学数奥题解法:
class Solution {
public int trailingZeroes(int n) {
int res = 0;
while(n != 0){
res += n/5;
n/=5;
}
return res;
}
}
时间复杂度就是 log_5(n)的操作
空间O(1)
厉害了
谢谢字幕员~