这个题目是编程之美上出现的,今年在几个公司笔试的时候都出现了这个题目,之前一直以为 直接用 N / 5 就是结果,昨天被土豆面试的时候,才发现自己理解错了,思路是这样的,0 的个数就是 1,,2,...,n中n个数中能够分解出5的因子的个数。之前以为 5,10,20,..., n/5 * 5 总共有 n/5个能够提出5的因子的,但是显然这里出现了问题,对于 25 这个数 = 5^2 能提出两个5的因子,所以应该会产生两个0。那我们该怎么解决这个问题呢,我们将5,10,20,....,n/5 * 5
提出一个因子5 ,5*1,5*2,5*3,5*4,5*5,5*(n/5)
即 5(1,,2,3,4,...,n/5) 后面括号中又会产生5,而且是按照前面同样的方式。 所有能够产生5的个数应该是:n/5+n/5/5+n/5/.../5,一直到某个数/5=0 。如对于n=2000,末尾0的个数为:
5 2000
5 400
5 80
5 16
3 ... 1
所有0的个数为 = 2000/5+ 400/5 + 80/5 + 16/5 = 400+80+16+3 = 499
好了,其实简单的程序如下:
int calcZero(int n) { int sum = 0; while(n / 5) sum+= n/5; return sum; }