讲两道常考的阶乘算法题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：讲两道常考的阶乘算法题

评论礼仪 见这里，违者直接拉黑。

[truemanchen]

trailingZeroes(mid)为啥要用两次； 这个写法我陷入了死循环哎！

[truemanchen]

是我写错了

[fkjkkll]

我有几点思考： 1、初始的hi设置为5k即可（当然还是要用long的，毕竟51e9放不进int里面） 2、这道题用普通二分搜索即可，找到满足条件直接返回5，因为答案要么是5要么是0

[labuladong]

@fkjkkll 👍

[Alwin4Zhang]

793. 【阶乘函数后 K 个零】 python version

class Solution:
    def preimageSizeFZF(self, k: int) -> int:

        def trailing_zeros(n):
            res = 0
            while n // 5 > 0:
                res += n // 5
                n = n // 5
            return res

        # 二分查找 左右边界
        def left_bound(target):  # target是有多少个满足条件
            # 左边界
            lo, hi = 0, 10e9
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if trailing_zeros(mid) < target:
                    lo = mid + 1
                elif trailing_zeros(mid) > target:
                    hi = mid
                else:
                    hi = mid
            return lo

        def right_bound(target):
            # 右边界
            lo, hi = 0, 10e9
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if trailing_zeros(mid) < target:
                    lo = mid + 1
                elif trailing_zeros(mid) > target:
                    hi = mid
                else:
                    lo = mid + 1
            return lo - 1

        return int(right_bound(k) - left_bound(k) + 1)

[cheng-miao]

daka

[lihuagang03]

打卡，感谢楼主！

[LebronHarden1]

谢谢

[NicholasIssac]

复杂度能这样分析的吗？那所有问题的n都小于某个常数，岂不是所有的复杂度都是常数了

[labuladong]

@NicholasIssac 比较小的数据可以这样分析，log(LONG_MAX) 最多不超过 64，当然可以认为是常数

[wqlbm]

这个结果只能是5呀。。。超过5个就会多一个0或者少一个0。

[MzxlM]

可以不用搜索右边界的 因为k+1 的左边界是 类似的东西

class Solution {
    public int preimageSizeFZF(int k) {
        return (int) (left(k+1) - left(k));
        // return (int)(right_bound(k) - left(k) + 1);

    }
    long left(int target) {
        long lo = 0, hi = Long.MAX_VALUE;
        while( lo < hi) {
            long mid = lo + (hi-lo)/2;
            if(trailingZeroes(mid) < target) {
                lo = mid +1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    
    // long right_bound(int target) {
    //     long lo = 0, hi = Long.MAX_VALUE;
    //     while (lo < hi) {
    //         long mid = lo + (hi - lo) / 2;
    //         if (trailingZeroes(mid) < target) {
    //             lo = mid + 1;
    //         } else if (trailingZeroes(mid) > target) {
    //             hi = mid;
    //         } else {
    //             lo = mid + 1;
    //         }
    //     }
    //     return lo - 1;
    // }
    
    public long trailingZeroes(long n) {
        long res = 0;
        for(long d = n; d/5 > 0; d = d/5) {
            res += d/5;
        }
        return res;
    }
}