Smallest Number With At least N Trailing Zeros In Factorial
Filed under Salesforce
Free read 2 of 3Understand that trailing zeros in a factorial are determined by the number of factors of 5 in the prime factorization of numbers up to x.
The question
Given a positive integer N, find the smallest non-negative integer x such that x! contains at least N trailing zeros.
Constraints
- 1 <= N <= 10^9
- Time complexity must be better than O(x) linear scan
Examples
- Input
- N = 6
- Output
- 25
- Why
- 25! has 6 trailing zeros (factors of 5 from 5, 10, 15, 20, 25 give 6 factors of 5).
Approach
Understand that trailing zeros in a factorial are determined by the number of factors of 5 in the prime factorization of numbers up to x.
Iterate x from 0 upwards, count trailing zeros of x!, and stop when count >= N. This is too slow for large N.
Use binary search on the range [0, 5 * N]. Count the number of trailing zeros for a mid value using Legendre's formula: count = mid/5 + mid/25 + mid/125 + ...
Handle N = 1 correctly (returns 5) and ensure correct handling of integer overflows during binary search bounds.
Solution
O(log(5N) * log_5(N)) time, O(1) space
class Solution:
def smallestFactorial(self, n: int) -> int:
def count_zeros(num):
count = 0
div = 5
while num >= div:
count += num // div
div *= 5
return count
low, high = 0, 5 * n
ans = high
while low <= high:
mid = (low + high) // 2
if count_zeros(mid) >= n:
ans = mid
high = mid - 1
else:
low = mid + 1
return ans
Tips
- What they are testing: Tests ability to combine math properties (Legendre's formula) with binary search.
- Common mistake: Linear scanning from 1 upwards, which results in Time Limit Exceeded (TLE).
Related Salesforce questions
Collected from public candidate posts and coding forums. Updated Nov 2026.