Preimage Size of Factorial Zeroes Function
HardMath
Description
Let f(x) be the number of trailing zeroes in x!. Given an integer k, return the number of non-negative integers x such that f(x) = k.
Examples
Input:
k = 0Output:
5Explanation:
0!, 1!, 2!, 3!, 4! have 0 trailing zeroes.
Input:
k = 5Output:
0Explanation:
Trailing zeroes jump from 4 (at 24!) to 6 (at 25!) because 25=5*5 contributes two factors of 5. No factorial has exactly 5 trailing zeroes, so the preimage size is 0.
Input:
k = 3Output:
5Explanation:
Trailing zeroes in x! come from factors of 10=2*5. Since factors of 2 are more abundant, trailing zeroes equal the count of factor 5 in x!. For f(x)=3: f(15)=3, f(16)=3, f(17)=3, f(18)=3, f(19)=3. Five values of x give exactly 3 trailing zeroes.
Constraints
- •
0 ≤ k ≤ 10^9
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.