LeetCode 793 Preimage Size of Factorial Zeroes Function

    
        标签：
        
            二分搜索
        
            数学类题目
        
            LeetCode
        
    发布于：2022-02-22 21:39:37
    编辑于：2022-02-22 22:36:03
    浏览量：1443

概述

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

Hard 哦。

二分搜索

首先，n! 的个末尾零的个数是知道的：

int trailingZeroes(int n) {
    int count = 0;
    int c = n;
    while (c / 5 != 0) {
        count += c / 5;
        c /= 5;
    }
    return count;
}

详见：https://iamazing.cn/page/leetcode-172-factorial-trailing-zeroes

显然该函数递增，那么就可以用二分查找求区间。

https://labuladong.gitee.io/algo/4/30/119/

先求左边界，再求右边界，最后算下差就好了。

属于是有些麻烦了。

O(logn * logn)

下面代码 WA（24 / 44 test cases passed），不想 debug 了，我好累：

class Solution {
public:
    int preimageSizeFZF(int k) {
        // find left bound
        long l = 0, r = LLONG_MAX;
        while (l < r) {
            long m = (r - l) / 2 + l;
            if (trailingZeroes(m) >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        long leftBound = l;
        // find right bound
        l = 0, r = LLONG_MAX;
        while (l < r) {
            long m = (r - l) / 2 + l;
            if (trailingZeroes(m) <= k) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        long rightBound = l;        
        return rightBound - leftBound;
    }
    
    int trailingZeroes(long n) {
        int count = 0;
        long c = n;
        while (c / 5 != 0) {
            count += c / 5;
            c /= 5;
        }
        return count;
    }
};

Links: leetcode-793-preimage-size-of-factorial-zeroes-function