factorial-trailing-zeroes

题目描述

给定一个整数 n，返回 n! 结果尾数中零的数量。

题解

乘积末尾能出现 0 的都是由 2*5 得到的，2的数量肯定比5多，因此只需要关注有多少个5就可以了。

1. 循环。每隔5个数出现一个5，每隔25个数出现两个5，每隔125个数出现三个5，……，因此5的个数是：$n/5+n/25+n/125+…$，代码如下：

   int trailingZeroes(int n) {
       int res=0;
       while(n>=5)
       {
           n/=5;
           res+=n;
       }
       return res;
   }

2. 递归。$f(n)=f(n/5)+n/5$，为什么能写成递归的形式？举个栗子，对于阶乘126!而言，数字126最接近的5的倍数是125，且$125 = 25x5$，也就是说对126!分解质因数，其一定能分解成$126! = 25x5 x 24x5 x 23x5 x 22x5 x…x 3x5 x 2x5 x 1x5 x…$形式，该式子中首先已经出现了25个5，但是仍需计算25!的阶乘中总共有多少个五，故可递归。
   链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/172-jie-cheng-hou-de-ling-di-gui-jie-fa-liang-xing/

   int trailingZeroes(int n) {
       if(n<5)return 0;
       return n/5+trailingZeroes(n/5);
   }