349. Smallest Number With at Least N Trailing Zeroes in Factorial

Given n, find the smallest positive integer x such that x! (x factorial) has at least n trailing zeroes in decimal.

Input: A single line containing the integer n. Output: Print a single integer - the smallest x such that x! has at least n trailing zeroes.

1 <= n <= 10^9

The trailing-zero COUNT function isn't strictly increasing (it can stay flat across several consecutive x values, like x=5 through x=9 all giving exactly 1 trailing zero) - this is exactly why the problem asks for the SMALLEST x achieving AT LEAST n, not exactly n, since some counts might be skipped entirely (like n values that no x produces exactly).

Find the smallest x such that x! (x factorial) has at least a given number of trailing zeroes. Brute force: Check every integer x starting from 0 upward, computing its trailing-zero count via Legendre's formula each time, stopping at the first one meeting the requirement - this works but is less elegant than directly binary searching for the exact boundary. Optimised: Since the trailing-zero count only ever increases (or stays flat) as x grows, binary searching directly on x - checking the monotonic 'count >= n' condition at each candidate via Legendre's formula (computed in O(log x)) - finds the exact smallest qualifying x in O(log(max x) * log(max x)).

Instead of recomputing the whole trailing-zero formula at every step, maintain a running zero count and, for each new x, add only the number of times 5 divides x itself (i.e. how many extra factors of 5 this specific x contributes). This still scans candidates one by one but does O(1) amortized extra work per step instead of a fresh O(log x) recomputation, making the scan itself faster while still being fundamentally linear in the answer. Time: O(ans) Space: O(1)

Starting from x = 1, repeatedly compute the number of trailing zeroes of x! from scratch using the formula floor(x/5) + floor(x/25) + floor(x/125) + ... (the count of factors of 5 in x!), and stop at the first x whose zero count is at least n. This is correct because the zero count is non-decreasing as x grows, but recomputing the full formula for every candidate x wastes work that was already done for x-1. Time: O(ans * log(ans)) Space: O(1)

The trailing-zero count of x! is a monotonically non-decreasing function of x, which means binary search can be used: for a candidate x, compute its zero count with the floor(x/5) + floor(x/25) + ... formula, and search over the range [0, 5*n] (since the zero count grows roughly like x/4, this range comfortably contains the answer) for the smallest x meeting the target. This avoids scanning every candidate individually, which matters enormously since n can be as large as 10^9. Time: O(log n * log(n)) Space: O(1)

1. Use Legendre's formula: the number of trailing zeroes in x! equals floor(x/5) + floor(x/25) + floor(x/125) + ... (counting how many multiples of 5, 25, 125, etc. contribute an extra factor of 5). 2. Notice this trailing-zero count is NON-DECREASING as x increases - a monotonic relationship perfect for binary search. 3. Binary search on x itself, over a safely bounded range (like 0 to 5*(n+1)), checking at each candidate whether its trailing-zero count meets or exceeds n.

Time: O(log(max x)²) - the binary search itself takes O(log(max x)) steps, and each step's Legendre's-formula computation takes O(log x). Space: O(1) - just a few counters.

Test n = 1 (smallest case) and n = 10^9 (largest case, requiring a formula-based trailing-zero count rather than computing factorials directly).

Be ready to derive Legendre's formula from first principles (why factors of 5, not 2, are the scarce resource limiting trailing zeroes, since factors of 2 are always more abundant in a factorial's prime factorization) - a common, valuable follow-up question.