Preimage of the
factorial zeroes

Count the x that land on exactly k trailing zeroes

Let f(x) = the number of trailing zeroes in x!. Given k (up to 10⁹), count the non-negative integers x with f(x) = k — the preimage of k. For k=0: 0!,1!,2!,3!,4! all end in no zero, so the answer is 5. For k=5: the answer is 0 — and understanding why is the whole problem.

Trailing zeroes are just factors of five

A trailing zero is a factor of 10 = 2 × 5. Inside 1 × 2 × … × x there are always more 2s than 5s, so fives are the bottleneck. Count them and you have the zero count — no giant number required:

f(x) = ⌊x/5⌋ + ⌊x/25⌋ + ⌊x/125⌋ + …

The extra terms matter because 25 = 5² hides two fives, 125 = 5³ hides three. So f(25) = 5 + 1 = 6, jumping straight past 5. That single jump is why k=5 has no preimage.

Flat fives, and the jump at 25

Plot f(x) for small x. Every level is five wide — until x = 25, where the count leaps from 4 to 6. Level 5 is a floor that no step ever lands on.

So the preimage size is always 5 or 0 — never 1, 2, 3, 4. If a level exists, five consecutive x's sit on it; if a jump skipped it, none do.

Two lower-bound searches, subtracted

The x's with f(x) = k form one contiguous block, so count it by its edges: lowerBound(k) (first x with f(x) ≥ k) and lowerBound(k+1). Each edge is a binary search over the number line [0, 5(k+1)] — no array, just the monotonic f. Watch one lower-bound search below: f(mid) ≥ target keeps the left half (answer could be mid); f(mid) < target discards it.

Try k=5 (both edges land on 25 → answer 0) or k=0 (edges 0 and 5 → answer 5). Switch the edge dropdown to watch each half of the subtraction.

Three values of k

For k=5, both edges snap to 25 because f never equals 5 — the subtraction returns 0 with no special-casing. The formula silently absorbs the skipped-level fact.

A helper, a boundary search, a subtraction

int preimageSizeFZF(int k) {
    return (int)(lowerBound(k + 1L) - lowerBound(k));
}

// first x with f(x) >= target
long lowerBound(long target) {
    long lo = 0, hi = 5L * (target + 1);
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (trailingZeroes(mid) >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

long trailingZeroes(long x) {
    long c = 0;
    while (x > 0) { x /= 5; c += x; }   // x/5 + x/25 + x/125 + …
    return c;
}

O(log² k) time, O(1) space. The outer search is O(log k) steps; each computes f(mid) in O(log₅ mid). Both edges together are two such searches.

Monotonic, so the predicate flips once

The preimage is one contiguous block precisely because f is monotonic. Its size is lowerBound(k+1) − lowerBound(k): where level k+1 starts, minus where level k starts. A skipped level makes both edges coincide, yielding 0 with no special case.

Six ways it slips

Binary search on the answer, not the array

There's no array here — the candidates are numbers in [0, 5k], probed by a monotonic predicate. That's binary search on the answer: choose a candidate, evaluate a monotone yes/no condition, discard half the numeric range. It's the clearest proof that binary search is a strategy for monotonic search spaces, not just sorted memory.

Two ideas stacked: replace an impossible computation with a factor count, then binary-search the monotone function's domain instead of enumerating inputs. That combination is what makes this more than a factorial puzzle.

Reconstruct it, don't memorize it

1. Trailing zeroes come from 2×5 pairs; factorials have surplus 2s, so count fives.
2. f(x) = x/5 + x/25 + x/125 + … — and it never decreases as x grows.
3. So the x's with f(x)=k form one contiguous block; binary-search its edges.
4. Count = lowerBound(k+1) − lowerBound(k), each a lower-bound search on [0, 5(k+1)] in long.
5. Because levels are five wide or skipped entirely, the answer is always 5 or 0.