Daily LeetCode – day0030 0793. Preimage Size of Factorial Zeroes Function

// 0793. Preimage Size of Factorial Zeroes Function
class Solution {
    public int preimageSizeFZF(int k) {
        long left = 0;
        long right = k * 5L;
        long middle;
        while (left < right) {
            middle = (left + right) / 2;
            int zeroes = trailingZeroes(middle);
            if (zeroes > k) {
                right = middle - 1;
            } else if (zeroes < k) {
                left = middle + 1;
            } else {
                left = middle;
                right = middle;
            }
        }
        if (trailingZeroes(left) == k) return 5;
        return 0;
    }

    private int trailingZeroes(long n) {
        int ans = 0;
        while (n != 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
}
学习笔记:
这道题用到了很多数学的内容,还有二分法内容。
这道题的基础先是0172. Factorial Trailing Zeroes这道中等题。
2因素肯定比5多,所以最后几个0得看有几个5参与运算了。
5,10,15,20这都还是1个5参与,但25,50,75,100可就有2个5了,125,250,375,500那就有3个5了。规律其实就是把那个数字除以5看一下还剩多少,加上去,再除以5看一下剩多少,一直除到0为止。
比如130的阶乘,
先除以5得26,答案先是26,代表有26个单个5参与了。(5,10,15,20……)
再除以5得5,答案先是31,代表有5个双个5参与了。(25,50,75,100,125)
再除以5得1,答案是32,代表有1个三个5参与了。(125)
就是这样层层计算可以得出130阶层最后有32个5参与运算,也就有32个零在最后。

接下来,回到本题!
我们要用二分法处理这道题目,left是0,这个很好理解,right是多少呢?直接写2147482647会超时的,所以得有合适的范围。
我们知道:
要有一个5参与运算,至少是5的阶乘,
要有两个5参与运算,至少是10的阶乘,
要有五个5参与运算,至少是25的阶乘,
但是要有六个5参与运算,还是至少是25的阶乘,因为25里有两个5。
要有十二个5参与运算,至少是50的阶乘。
所以这个至少几的阶乘,一定是会小于5的数量的五倍的。
这一点我很难想通,但是现在起码想通了,如果再想不通得看上面这段例举了。
因此右边界就确定是k*5了,但这道题最后一个样例坑爹了是1000000000,乘完会越界然后结果就不对了,这个得需要用到long。
我在二分法求出结果后做的校验方案就是如果那这个left去求解,刚好是k,那么说明存在,也就是会有5个数字,可能是01234结尾也可能是56789结尾。
但如果不等于k,那说明不存在,也就是一下子阶乘计算中乘了一个带有多个5的数字。

真是一道特别绕的题目,虽然只是小学数学,但数学思路不太好的笨蛋绕到死也会解不开的吧。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

Daily LeetCode – day0030 0793. Preimage Size of Factorial Zeroes Function》有2条回应

  1. anna说:

    Yiqun, you are the best.

发表回复

您的电子邮箱地址不会被公开。