Preimage Size of Factorial Zeroes Function

Preimage Size of Factorial Zeroes Function

What is this problem about?

The Preimage Size of Factorial Zeroes Function problem asks: how many non-negative integers n satisfy trailingZeroes(n!) = k? Here, trailingZeroes(n!) counts trailing zeros in n! (which equals the count of 5s in n!'s prime factorization). This hard coding problem uses binary search to find the range of n values mapping to exactly k zeros. The math and binary search interview pattern is the core.

Why is this asked in interviews?

Adobe asks this because it chains two concepts: the trailing zeroes formula (count of factors of 5 in n!) and binary search to find preimage sizes. Trailing zeroes f(n) is monotonically non-decreasing, enabling binary search.

Algorithmic pattern used

Trailing zeroes formula + binary search. trailingZeroes(n) = n//5 + n//25 + n//125 + .... Since f is monotonically non-decreasing, binary search finds the smallest n where f(n) ≥ k and the smallest n where f(n) ≥ k+1. The answer is rightBound - leftBound where leftBound = first n with f(n)=k, rightBound = first n with f(n)=k+1. Answer is 0 or 5 (always 0 or 5 due to the 5-step nature of trailing zeros).

Example explanation

k=0. f(1)=0, f(5)=1. Numbers with 0 trailing zeros: 0,1,2,3,4. Binary search: leftBound for f(n)≥0 = 0; rightBound for f(n)≥1 = 5. Answer = 5-0 = 5.

k=1. f(5)=1, f(10)=2. Numbers 5,6,7,8,9 all have f=1. Answer = 5.

k=5. f(25)=6. No n has exactly 5 trailing zeros (jump from 4 to 6). Answer = 0.

Common mistakes candidates make

• Off-by-one in binary search bounds.
• Not handling the "gap" in trailing zeros (some k values like 5 have no preimage).
• Incorrect trailing zeros formula (forgetting powers beyond 5²).
• Binary search upper bound too small (need up to 5*(k+1) approximately).

Interview preparation tip

Preimage Size of Factorial Zeroes requires chaining trailing zeros formula with binary search. The answer is always 0 or 5 because factorial trailing zeros skip some values (e.g., 5 to 6 at n=25). Practice the trailing zeros formula independently: sum(n//5^i for i in 1,2,...). Then apply binary search for the range of n with a given value. This pattern appears in "count digits in range" and "count primes in factorial range."