LeetCode 793 Preimage Size of Factorial Zeroes Function

Tag: 二分搜索 数学类题目 LeetCode Posted on 2022-02-22 21:39:37 Edited on 2022-02-22 22:36:03 Views: 171

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/