讲两道常考的阶乘算法题 :: 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

[bert82503]

打卡，感谢楼主！

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

[yonggui-yan]

打卡。

当找到>=k的左边界后left，>=(k+1)的做边界只能是 left 或者left+5.

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def zeros(n):
            n_0 = 0 
            while n > 0:
                n = n//5
                n_0 += n
            return n_0
        
        
        # print(zeros(10000000000)>pow(10,9)) 
        
        def find_k(left, right, k):
            #返回大于等于k的最小值
            while left<right:
                mid = left + (right-left)//2  
                n0 = zeros(mid)
                if n0>k:
                    right = mid
                elif n0<k:
                    left = mid + 1
                else:
                    right = mid
                     
            return left
            
        left = find_k(0, 10000000000, k)
        right = find_k(left, left+5, k+1)
        
        # print(left, right) 
        
        return right-left

[yonggui-yan]

或者， 只要验证 zeros(left), 即可决定返回5 还是0.

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def zeros(n):
            n_0 = 0 
            while n > 0:
                n = n//5
                n_0 += n
            return n_0
        
        
        # print(zeros(10000000000)>pow(10,9)) 
        
        def find_k(left, right, k):
            #返回大于等于k的最小值
            while left<right:
                mid = left + (right-left)//2  
                n0 = zeros(mid)
                if n0>k:
                    right = mid
                elif n0<k:
                    left = mid + 1
                else:
                    right = mid
                     
            return left
            
        left = find_k(0, 10000000000, k)
        
        if zeros(left)==k:
            return 5
        else:
            return 0 

[lapchinglin]

为什么这里需要用while(left < right )而不是while(left <= right)?

[teugerbxlu]

二分法lo的初始值设4k就行

[mangohow]

我们只需要搜索有没有一个数的阶乘的结果的0的个数为k个，如果存在这个数，那么它前面四个肯定也是可以的，返回值要么是0要么是5.
搜索的时候只需要搜索5的倍数就行了，如果能找到，就返回5，否则就返回0。因此只需要在[0,k]的范围内搜索即可

func preimageSizeFZF(k int) int {
	// 返回值只有两种：0或5
	// 使用二分搜索
	left, right := 0, k
	for left <= right {
		mid := left + (right-left)/2
		n := trailingZeroes(mid * 5)
		if k < n {
			right = mid - 1
		} else if k > n {
			left = mid + 1
		} else {
			return 5
		}
	}

	return 0
}

func trailingZeroes(n int) int {
	res := 0
	divisor := 5
	for divisor <= n {
		res += n / divisor
		divisor *= 5
	}
	return res
}

[mangohow]

不好意思写错了，是一旦找到该数，那么它后面四个数也是可以的，因此后面四个数不会贡献出更多的5

[lzfeifei]

"够了吗？我们发现 125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出 125! 中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。"

这里不太明白，125 / 125 = 1 ，不应该是能提供1*3=3个因子5吗？？