样例
11! = 39916800,因此应该返回 2
这一题,看着很水,但是要是没有做过的话,也会 遇到很多的坑,我就是这样(难受),这道题虽然非常简单,但是非常的考察人,第一种算法就是最low,最暴力的方法,简单粗暴的计算能被分解的5的个数:
public static long num(long n){ if (n < 5){ return 0; } long num = 0; for (long i = 5;i <= n;i++){ long t = i; while (t%10==0&&t!=0){ num++; t = t/10; } while (t%5 == 0&&t!=0){ num++; t = t/5; } } return num; }这种算法的复杂度是0(n),很明显 超时了;
我就想要是我把每次的步数调整为5那时间复杂度不就是O(n)/5
public static long num(long n){ if (n < 5){ return 0; } long num = 0; for (long i = 5;i <= n;i+=5){ long t = i; while (t%10==0&&t!=0){ num++; t = t/10; } while (t%5 == 0&&t!=0){ num++; t = t/5; } } return num; }可是我又天真了,还是超时,因为O(n)约等于O(n)/5;
最后参考了一下某网友的方法如下:
public static long num(long n){ long num = 0; long t = n/5; while (t!=0){ num+=t; t = t/5; } return num; }这个算法的时间复杂度为O(n);
我又写了下面同样 复杂度的方法:
public static long num(long n){ long num = 0; while (n!=0){ long t = n/5; num+=t; n = n/5; } return num; }