Preimage Size of Factorial Zeroes Function — Hard Problem & Solution

Let f(x) be the number of trailing zeros in x!. For instance f(3) = 0 because 3! = 6, and f(11) = 2 because 11! = 39916800.

Difficulty: Hard
Topics: Math, Binary Search, Number Theory
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Let f(x) be the number of trailing zeros in x!. For instance f(3) = 0 because 3! = 6, and f(11) = 2 because 11! = 39916800.

Given k, return how many non-negative integers x satisfy f(x) == k.

Example 1

Input: k = 0
Output: 5
Explanation: f(x) = 0 for x in {0, 1, 2, 3, 4}.

Example 2

Input: k = 5
Output: 0
Explanation: f jumps from 4 (at x = 20…24) to 6 (at x = 25), skipping 5 entirely.

Example 3

Input: k = 3
Output: 5
Explanation: f(x) = 3 for x in {15, …, 19}.

Constraints

0 <= k <= 1000000000

How to solve Preimage Size of Factorial Zeroes Function

f is a step function that is constant on each block of five consecutive integers and jumps at every multiple of 5. So each value it attains is attained exactly five times, and values it skips are attained zero times.

Approach

Implement f(x) as the Legendre sum x/5 + x/25 + x/125 + ….
Binary search the smallest x >= 0 with f(x) >= k, using 5(k + 1) as a safe upper bound.
Return 5 if f(x) == k, otherwise 0.

Why it works

Between consecutive multiples of 5 no new factor of five appears, so f is constant across each block of five. At a multiple of 5 it jumps by at least 1 — by more at multiples of 25 — which is exactly why some values of k are skipped. The upper bound works because f(5(k+1)) >= k + 1 > k.

Complexity

Time — O(log k · log k)
Space — O(1)

Pitfalls

The search space reaches about 5 × 10^9, which overflows a 32-bit integer — use 64-bit bounds.
p *= 5 also overflows if the loop is not stopped once p > x.
Answering 1 for a value that is attained ignores the five-wide plateau.

Reference solution

Python

def preimageSizeFZF(k: int) -> int:
    def zeros(x: int) -> int:
        total = 0
        p = 5
        while p <= x:
            total += x // p
            p *= 5
        return total

    lo, hi = 0, 5 * (k + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        if zeros(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return 5 if zeros(lo) == k else 0

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue