Smallest number whose factorial has at least n trailing zeros

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}