阶乘问题

一、题目

给定一个非负整数 N，返回 N! 结果的末尾为 0 的数量。例如 3! = 6，结果的末尾没有 0，则返回 0。5! = 120，结果的末尾有 1 个 0。返回 1。

二、分析

末尾为 0 说明可以凑成 10，又因为一个数中如果有 5 的因子，那么一定会有 2 的因子。因此我们只需要求 1,2,3, ..., N-1,N，这 N 个数中一共有多少个因子 5。因子 2 的数目比因子 5 的数目多，所以不管有多少个因子 5，都有足够的因子 2 可以与其相乘得到 10。所以这个问题我们只需要求 1 - N 所有的数中，一共含有多少个因子 5 就可以。

int zeroNum1(int num) {
		if (num < 0) {
				return 0;
		}
		int res = 0;
		int cur = 0;
		for (int i = 5; i < num+1; i=i+5) {
				cur = i;
				while (cur % 5 == 0) {
						res++;
						cur /= 5;
				}
		}
		return res;
}

以上的方法对于每一个数 i 来说，处理的代价是 logi（以 5 为底），一共有 N 个数，所以时间复杂度为：O(N*logN)

下来，我们优化一下，我们发现

每 5 个含有 0 个因子的数 (1,2,3,4,5)组成一组，这一组中的第 5 个数就含有 5^1 的因子 5
如果每 5 个含有 1 个因子 5 的数 (5,10,15,20,25)组成一组，这一组中的第 5 个数就含有 5^2 的因子 25
如果每 5 个含有 2 个因子 5 的数 (25,50,75,100,125)组成一组，这一组中第 5 个数就含有 5^3 的因子 125
因此，如果每 5 个含有 i 个因子 5 的数组成一组，这一组中第 5 个数就含有 5^(i+1) 的因子

所以，如果把 N! 的结果中因子 5 的总个数记为 Z，就可以得到如下关系：

1	Z = N/5 + N/(5^2) + N/(5^3) + ... + N/(5^i) (i 一直增长，直到 5^i > N)

也就是说，1 - N 中有 N/5 个数，这每个数都能贡献一个 5；然后 1-N 中有 N/(5^2) 个数，这每个数又都能贡献一个 5。依次类推，其实还是在求每个数有多少个因子 5。

int zeroNum2(int num) {
		if (num < 0) {
				return 0;
		}
		int res = 0;
		while (num != 0) {
				res += num / 5;
				num /= 5;
		}
		return res;
}

可以看到，一共有 N 个数，最优解的时间复杂度为 O(logN)，以 5 为底。

三、进阶问题

给定一个非负整数 N，如果用二进制表达 N! 的结果，返回最低位的 1 在那个位置上，认为最右的位置为 0。例如：1! = 1，最低位的 1 在 0 位置上。2! = 2，最低位的 1 在 1 位置上。

分析：最低位的 1 在那个位置上，完全取决于 1-N 的数中因子 2 有多少个，因为只要出现一个因子 2，最低位的 1 就会左移一位。所以，如果 N! 的结果中因子 2 的总个数记为 Z，我们就可以得到如下关系：

1	Z = N/2 + N/4 + N/8 + ... + N/(2^i) (i 一直增长，直到 2^i > N)

因此很容易得到代码：

int rightOne(int num) {
		if (num < 1) {
				return -1;
		}
		int res = 0;
		while (num != 0) {
				num >>= 1;
				res += num;
		}
		return res;
}

四、leetcode 题目

阶乘后的零： https://leetcode.cn/problems/factorial-trailing-zeroes/

阶乘尾数： https://leetcode.cn/problems/factorial-zeros-lcci/