793. Preimage Size of Factorial Zeroes Function

Link

Solution

發現有一個單調性，當 num! 的zero數 > K 時， (num+1)!的zero數也會> K

答案可以簡化成:

所有zero數在K以下的數- 所有答案在K-1以下的數。

用binary search找出某數num使得 f(num) <= K

然後找出 num & num2使得

f(num) <= K

f(num2) <= K-1

答案即是 num - num2

 public int preimageSizeFZF(int K) {
        return (int)(findNum(K) - findNum(K-1));    
    }
    
    //find the num which f(num) <= K
    public long findNum(int K){
        long start = 0, end = 5L * (K+1); //K+1為了避免 K = 0的case
        
        while(start < end){
            long mid = start + (end - start)/2;
            if(isMoreThan(mid, K)){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        //start will be the smallest num which f(num) > K
        return start-1;
    }
    
    public boolean isMoreThan(long mid, int K){
        int res = 0;
        while(mid > 0){
            res += (int)mid/5;
            mid = mid/5;
        }
        return res > K;
    }