Leetcode-793. 阶乘函数后K个零

793. 阶乘函数后K个零
f(x) 是 x! 末尾是0的数量。（回想一下 x! = 1 * 2 * 3 * ... * x，且0! = 1）

例如， f(3) = 0 ，因为3! = 6的末尾没有0；而 f(11) = 2 ，因为11!= 39916800末端有2个0。给定 K，找出多少个非负整数x ，有 f(x) = K 的性质。

示例 1:
输入:K = 0
输出:5
解释: 0!, 1!, 2!, 3!, and 4! 均符合 K = 0 的条件。

示例 2:
输入:K = 5
输出:0
解释:没有匹配到这样的 x!，符合K = 5 的条件。
注意：

K是范围在 [0, 10^9] 的整数。
解题思路
我们知道随着n增大，阶乘0的个数是单调递增的。那么我们利用5的阶乘求出有几个0.
剩下的就可以用二分查找找到0的个数等于k的左右边界，然后右边界减左边界+1就是问题所求
二分查找的下限为0，上限由k决定。k的最大值为10^9，则int的最大值会溢出，应该选择long的最大值

class Solution {
    public int preimageSizeFZF(int K) {
        //trailingZeroes(n) == K 的右侧边界-左侧边界加上1.就是中间有多少等于k
        return (int)(right_bound(K)-left_bound(K))+1;
    }
    public long trailingZeroes(long n){

        long res=0;
        for(long d=n;d/5>0;d=d/5){
            res+=d/5;
        }
        return res;
    }
    ///* 搜索 trailingZeroes(n) == K 的左侧边界 */
    public long left_bound(int target){
        long li=0;
        long ri=Long.MAX_VALUE;
        while(li<ri){
            long mid=(ri-li)/2+li;
            if(trailingZeroes(mid)<target){
                li=mid+1;
            }
            else{//大于等于一定不是左边界（前一个不一定，所以不能mid-1）
                ri=mid;
            }
        }
        return li;
    }
    //最后让li指向最右侧边界
    public long right_bound(int target){
        long li=0;
        long ri=Long.MAX_VALUE;
        while(li < ri){
            long mid=(ri-li)/2+li;
            if(trailingZeroes(mid)>target){
                ri=mid;
            }else{//li需要指向>k的，所以<=k,则直接右移li
                li=mid+1;
            }
        }
        return li-1;
    }
}