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);
        }
    }
}


回到顶部