本文主要是介绍Leetcode#172. Factorial Trailing Zeroes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:给定一个整数 n,计算 n! 末尾有多少个0
解题思路:虽然代码只有短短几行,但问题的解决是需要技巧的。
- 首先明确一个问题,n! 末尾若有0出现,那么一定是 2 * 5得来的,所以如果我们知道了 n! 中有多少个 2 * 5,那么就知道了末尾有多少个0;
接下来,我们就想一想n! 中有多少个 2 * 5?有一个事实,在 n! 中,2的个数一定是大于5的个数的,有博主给出了证明,如下:
对于阶乘而言,也就是1*2*3*…*n
[n/k]代表1~n中能被k整除的个数
那么很显然,[n/2] > [n/5] (左边是逢2增1,右边是逢5增1)
[n/2^2] > [n/5^2] (左边是逢4增1,右边是逢25增1)
……
[n/2^p] > [n/5^p] (左边是逢2^p增1,右边是逢5^p增1)
随着幂次p的上升,出现2^p的概率会远大于出现5^p的概率。
因此左边的加和一定大于右边的加和,也就是n!质因数分解中,2的次幂一定大于5的次幂。因此问题就简单了,我们只需要知道 n! 中有多少个5就可以了,比如n = 5,那么就有一个5;n = 25,那么就有来自5,10,15,10,25(有2个5,一定要注意!)的6个5。在计算 n! 中有几个5的时候需要注意。
C++实现如下:
class Solution {
public:int trailingZeroes(int n) {int ret = 0;while(n){ret = ret + n / 5;n = n / 5;}return ret;}
};
这篇关于Leetcode#172. Factorial Trailing Zeroes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!