阶乘零点函数的前像大小-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 求n!末尾有k个0的n有多少个

思路：

- 因式分解，末尾有0肯定是2*5，不管n是多大，n!分解因式后，2的个数肯定比5的个数多
- 假设给定n，如何求n!分解因式后有多少个5？每隔5个数贡献一个5因子，每隔25个数有多贡献一个5因子。。。统计能得到结果
- 这个题的做法是二分一个范围区间，求出n!分解因式后因子5的个数等于k的上下界，相减所得
- 这个题有个可优化的点，答案要么是0，要么是5，因为每隔5个数肯定会贡献一个5因子。那么我们只需要一个二分，找出是否有一个n，分解因式后有k个5因子，就可以返回5，否则返回0

解法：

```java
class Solution {
	 private long cal5(long n) {
        long ret = 0;
        while (n != 0) {
            ret += n / 5;
            n /= 5;
        }
        return ret;
    }

private long upper(long left, long right, int k) {
        while (right - left > 1) {
            long mid = (left + right) / 2;
            if (cal5(mid) <= k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (cal5(left) == k) {
            return left;
        } else {
            return -1;
        }
    }

private long lower(long left, long right, int k) {
        while (right - left > 1) {
            long mid = (left + right) / 2;
            if (cal5(mid) >= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (cal5(right) == k) {
            return right;
        } else {
            return -1;
        }
    }

public int preimageSizeFZF(int K) {
        long n = upper(1, 6000000000L, K);
        if (n == -1) {
            return 0;
        } else {
            long m = lower(-1, n, K);
            return (int) (n - m + 1);
        }
    }
}
```

该分类下的相关小册推荐：

业务开发实用算法精讲

编程之道-算法面试(上)

编程之道-算法面试(下)

算法面试通关 50 讲

数据结构与算法(上)

数据结构与算法之美

数据结构与算法(下)