793. Preimage Size of Factorial Zeroes Function

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 2 3 … x and by convention, 0! = 1.

• For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

class Solution {
    long long count(long long m) {
        long long res = 0;
        while(m >= 5) {
            res += m = m / 5;
        }
        return res;
    }
    long long helper(int k) {
        if(!k) return 5;
        long long l = 0, r = LLONG_MAX;
        while(l <= r) {
            long long m = l + (r-l) / 2, cnt = count(m);
            
            if(cnt > k) r = m - 1;
            else l = m + 1;
        }
        return l - 1;
    }
public:
    int preimageSizeFZF(int k) {
        if(!k) return 5;
        return helper(k) - helper(k-1);
    }
};