前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定正整数num，求num的阶乘结果中，0的个数
如: num = 5
5！ = 120
因此结果为1
进阶问题
给定正整数num，求num的阶乘结果转成二进制后，最右边1的位置
如 num = 2
结果为1

解决方案

原问题：
首先结果中的每一个0和2都是 [1…num]中2和5的贡献，因此求出有多少对2和5，即可知道结果中有多少个0
1、首先1…num中2的个数坑定是比5多的，毋庸置疑，因此问题转化成了求1…num中因子5的个数
2、首先因子5的个数存在于 5,10,15,20,25 … 125 … 5^logn，底为5
3、其中至少有一个5的因子（5^logn）/5，至少有2个5的因子 （5^logn）/25 …以此类推，最终5的个数公式:
（5^logn）/5 + （5^logn）/25 + … （5^logn）/（5^logn）

进阶题目
首先结果中每一个0的个数都是2的贡献，因此只需要求出(1…num中有多少个2)即可
1、首先定义z为1…num中2的个数，num的二进制中1的个数记录为m，那么存在一个公式：
z = num - m, 证明后补

代码编写

java语言版本

原问题：
方法一:

    /* 二轮测试：求n!中结果中有多少个0* @param n* @return*/public static int getZeroNumsCp1(int n) {if (n <= 0) {return 0;}int value = n;int res = 0;while (value != 0) {res += value/5;value /= 5;}return res;}/* 二轮测试：求n！中的二进制表达中，最右边的1的位置* 每出现一个2的因子就会出现一个0，所以计算出2因子的个数即可* @param n* @return*/public static int getOneIndexCp1(int n) {if (n <= 0) {return 0;}int value = n;int res = 0;while (value != 0) {res += value >>> 1;value >>>= 1;}return res;}/* 二轮测试：求n！中的二进制表达中，最右边的1的位置* 解法二：根据 结果=n-n中1的个数* @param n* @return*/public static int getOneIndexCp2(int n) {if (n <= 0) {return 0;}int value = n;int ones = 0;while (value != 0) {value -= value & (~value + 1);ones++;}return n - ones;}public static void main(String[] args) {System.out.println(getOneIndexCp2(2));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题玩的数学，首先先介绍计算5的个数：
5,10,15,20,25 … 125 … 5^logn 中5的个数不好求，我一般对于普遍性规律可以自行先造一个小的具体例子
比如求 5…125中5的个数
我们知道从5开始一直到125，有因子5的有5,10,15,20,25…50…75…100…125，我们记录一条线
\\5–10—15—20–25—30–35-----------50---------75----------100----------125 一共有 125/5个
接下来记录存在2个5的
----------------------25----------------------50----------75----------100----------125 一共有125/25个
接下来记录存在3个5的
只有125
所以横向来看，最终的5因子个数就是 125/5 + 125/25 + 125/125

二、接下来看下进阶问题的证明
首先求2的个数和求5的个数是一样的公式
num/2 + num/4 + num/8…num/lognum（2为底）
那么接下来问题就变成了：
num - m = num/2 + num/4 + num/8…num/lognum
首先能够得到一个问题就是这里的num/2不是严格意义的除法，而是向下取整的除法，因为都是int类型
因此num/2 + num/4 + num/8…num/lognum通过等比数列求和公式最终结果为num-1
接下来看如果num中存在m个1，那么num = k1 + k2 + k3 …kn （其中kn为2的某次方）
num/2 + num/4 + num/8…num/lognum
= （k1 + k2 + k3 …kn）/2 + （k1 + k2 + k3 …kn）/4 + （k1 + k2 + k3 …kn）/8…（k1 + k2 + k3 …kn）/lognum
=k1/2 + k1/4+k1/8 … （kn/2） + kn/4
=k1 - 1 + k2 - 1 … kn -1
= num - m
证明完毕

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！