给定一个int n,返回n的阶乘的末尾连续的零的个数。保证n为正整数。
测试样例:
5
返回:1
/* * 思路:刚开始做这道题的时候,我是先求出n!再计算有多少个0 * 这样的复杂度很大,编译不通过,后来在编程之美中看到了思路,思路如下 * n!可以质因数分解,由于2*5=10,所以尾零的个数只与2和5有关 * 但是能被2整除的频率比被5整除的数高的多,所以尾零的个数其实只和5相关, * n!能被多少个5解,就有多少个0, * 这事,通过遍历(1到n)只要将能被5整除,就统计+1,最后统计的数,就是尾零的个数 * */ public class Factor { public int getFactorSuffixZero(int n) { int count=0; for (int i = 1; i <=n; i++) { int j = i; while(j%5==0){ count++; j/=5; } } return count; } }
import java.util.*; /* 思路:只要出现了一个0,那这个0就不会消失。2*5=0,然后整10会多一个0,于是就没有别的成0了,那简单啊 n如果是18,那就是2*5=1个0,10=1个0,12*15=1个0,看有几组2*5和整10即可 因为有2必有5,有2没5也构不成10,因此看2*5不如看5的数目,而且整10也可以算一个,但整10也就是5*2,也可以看成一组5*2 因此只用看5的数目就可以,有多少个5就是多少个0,但是有点要搞清楚25是两个5,125是3个5,不能都当成1个5来用 当时简单的以为只要是尾数是5的那都是1个5,但是细细想来就可以意识到分解25可以提供两个5,而另一个5去乘4就能得到0, 得到0的数目只跟5有关系,偶数是源源不断的,但5的数目少的可怜,因此只用关注5即可 说是说2*5得到0,实际上是任意一个偶数乘5得到0,因此题目最终分解为n/5+n/25+n/125...直到/5之后等于0 叽里咕噜的说了一大堆,其实都是自己总结自己对这题目的分析,大家挑自己能看懂的部分看就好,写的没什么逻辑性 */ public class Factor { public int getFactorSuffixZero(int n) { int count =0; while(n>=5){ count+=n/5; n=n/5; } return count; } 运行时间:16ms 占用内存:8440k
import java.util.*; import java.math.*; public class Factor { public int getFactorSuffixZero(int n) { BigDecimal a = new BigDecimal(1); int target = 0; for(int i = 1;i<=n;i++){ a = a.multiply(new BigDecimal(i)); } BigDecimal bigDecimal = new BigDecimal(0); BigDecimal bigDecimal1 = new BigDecimal(10); while(a.compareTo(bigDecimal)>0){ if(a.divideAndRemainder(bigDecimal1)[1].compareTo(bigDecimal)>0){ target++; a = a.divide(bigDecimal1); }else{ break; } } return target; } }
class Factor { public: int getFactorSuffixZero(int n) { // write code here int sum=5,count=0; while(sum<INT_MAX/5&&sum<=n) { count+=n/sum; sum*=5; } return count; } };5*2产生一个0,25*4产生2个0,125*8产生3个0,625*16产生4个0,625是5、25、125的除数,125是25、5除数,25是5的除数。最后从1+2+3+4个0可以变成------4个5的除数+3个25的除数+2个125的除数+1个625的除数,4+3+2+1个0 ,也就是变成求这些数的个数,记得检测边界防止溢出
思路:有5必定有0 class Factor { public: int getFactorSuffixZero(int n) { int count =0; while(n>=5){ count+=n/5; n=n/5; } return count; } };
其实就是求5的个数,5提供一个5,25提供2个,125提供3个,如此类推。第一轮除以5,表示所有能提供5的都拿出一个来,此时25还能提供一个5,125还能提供2个5。。。直到最后n为0,表示不能在提供5,就返回0
class Factor {
public:
int getFactorSuffixZero(int n) {
return n?n/5+getFactorSuffixZero(n/5):0;
}
//非递归版本
int getFactorSuffixZero1(int n) {
// write code here
int res = 0;
while (n) {
n/=5;
res += n;
}
return res;
}
};
class Factor { public: /* @author:yishuihan 思路说明:首先如果求出阶乘,那么int型变量很快就溢出了;所以不能直接计算; 如果形成0,那么要么就是2*5这样的因子。(哪怕是10,也可以看出2*5) 所以,题目求出2和5的因子对数,而2的数量肯定大于5的数量 (这个肯定的,因为一个数假如能被2整除,得到的结果肯定比被5整除得到的个数多), 所以题目求5的因子个数。从5开始,然后25,然后125..... */ int getFactorSuffixZero(int n) { // write code here if(n<=1) return 0; int count=0; for(int i=5;n/i>0 ;i*=5) count+=n/i; return count; } };
class Factor { public: /* 10 = 2*5,阶乘是所有数相乘,所有相当于求min(2的因子数,5的因子数) // 由于2出现频率必然大于5,所以等价于求n!素数分解后5的因子数 // 一个数提供的因子5的个数等于 //将其转化成5进制后,后缀0的个数,如20 -> 40 可以提供1个5,1000可以提供3个 // 由此只要把1-N转成5进制求第一个非0的位置,求和即可 // 有一种简便方法, //如360326转为5进制是43012301,忽略最低位的1得到43012300 右移1位得到4301230,则有4301230个数(1,2,...,4301230)起码能提供1个0 再右边1位430123则这些能再提供1个0 ... // */ int getFactorSuffixZero(int N) { // write code here int base = 5; int num = 0; while(N>=base){ N/=base; num+=N; } return num; } };
class Factor { public: int getFactorSuffixZero(int n) { // write code here int count = 0; int base = 5; while(base <= n) { count += n/base; base *= 5; } return count; } };
import java.util.*; public class Factor { public int getFactorSuffixZero(int n){ // write code here int cnt = 0; while((int)(Math.pow(5,cnt))<=n){ cnt++; } int out = 0; cnt--; while(cnt>0){ out+= n/(int)(Math.pow(5,cnt)); cnt--; } return out; } }计算n里面5的个数、25的个数。。。。然后相加(2 肯定比5要多的,这个不用验证)