Preimage Size of Factorial Zeroes Function

hard binary-search math

Problem

Let f(x) be the number of trailing zeroes in x!. Given k, return how many non-negative integers x satisfy f(x) == k. The answer is always 0 or 5.

Inputk = 0

Output5

0!, 1!, 2!, 3!, 4! all end in 1, so five values give 0 trailing zeroes.

def preimageSizeFZF(k):
    def zeta(x):
        r = 0
        while x:
            x //= 5
            r += x
        return r
    lo, hi = 0, 5 * (k + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        if zeta(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return 5 if zeta(lo) == k else 0

var preimageSizeFZF = function(k) {
    const zeta = (x) => { let r = 0; while (x) { x = Math.floor(x / 5); r += x; } return r; };
    let lo = 0, hi = 5 * (k + 1);
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (zeta(mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return zeta(lo) === k ? 5 : 0;
};

class Solution {
    private long zeta(long x) { long r = 0; while (x > 0) { x /= 5; r += x; } return r; }
    public int preimageSizeFZF(int k) {
        long lo = 0, hi = 5L * (k + 1);
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (zeta(mid) < k) lo = mid + 1;
            else hi = mid;
        }
        return zeta(lo) == k ? 5 : 0;
    }
}

class Solution {
    long long zeta(long long x) { long long r = 0; while (x) { x /= 5; r += x; } return r; }
public:
    int preimageSizeFZF(int k) {
        long long lo = 0, hi = 5LL * (k + 1);
        while (lo < hi) {
            long long mid = (lo + hi) / 2;
            if (zeta(mid) < k) lo = mid + 1;
            else hi = mid;
        }
        return zeta(lo) == k ? 5 : 0;
    }
};

Explanation

The answer to this problem is always either 0 or 5, which feels surprising until you see why. As x increases, the number of trailing zeroes in x! stays flat for a while and then jumps — and whenever it lands on a value, it stays there for exactly five consecutive integers before jumping again.

The helper zeta(x) counts trailing zeroes of x! by repeatedly dividing by 5 and summing (x/5 + x/25 + ...), because each trailing zero comes from a factor of 5. This function is non-decreasing, which is exactly what lets us binary search.

We binary search for the smallest x where zeta(x) >= k. If zeta(mid) < k we need a larger x (lo = mid + 1); otherwise we pull hi = mid. After the loop, we check that lo actually hits k: if zeta(lo) == k the answer is 5, otherwise k is skipped entirely and the answer is 0.

Example: k = 0. We want the smallest x with zeta(x) >= 0, which is x = 0, and zeta(0) = 0 == k. So exactly five values — 0, 1, 2, 3, 4 — give zero trailing zeroes, and the answer is 5.

Since zeta itself loops about log x times and the binary search adds another log factor, the whole thing runs in roughly log^2 k time.

Time: O(log^2 k) Space: O(1)