Skip to content

793. Preimage Size of Factorial Zeroes Function

793. Preimage Size of Factorial Zeroes Function

题目: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/

难度: 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

解法：

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);
        }
    }
}
回到顶部