Smallest number whose factorial has at least n trailing zeros
Problem
Return the smallest integer m such that m! ends with at least n zeros.
Example 1
Input: n = 1 Output: 5
5! = 120.
Example 2
Input: n = 6 Output: 25
25! has 6 trailing zeros, but 24! has only 4.
Also asked as: Smallest number with atleastn trailing zeroes infactorial
Test cases
Case 1
Input: 1 Expected: 5
Case 2
Input: 6 Expected: 25
Case 3
Input: 5 Expected: 25
Case 4
Input: 3 Expected: 15
View solutionHide solution1 approach
1. Binary search + Legendre's formula (count factors of 5)
Time O(log²(n))Space O(1)
Trailing zeros in m! = floor(m/5) + floor(m/25) + … Binary-search the smallest m whose count ≥ n.
function smallestFactorialWithZeros(n) { const zeros = (m) => { let c = 0; for (let p = 5; p <= m; p *= 5) c += Math.floor(m / p); return c; }; let lo = 0, hi = 5 * n; while (lo < hi) { const mid = (lo + hi) >> 1; zeros(mid) < n ? (lo = mid + 1) : (hi = mid); } return lo;}