786. The Smallest Factorial Ending in k Zeros
Given k, print the smallest positive integer p such that p! ends in EXACTLY k zeros. If
no such p exists, print -1.
1 -> 5 5! = 120
3 -> 15 15! ends in three zeros
6 -> 25 25! ends in six zeros, because 25 contributes two fives
5 -> -1 no factorial ends in exactly five zeros
## Counting the zeros without building the factorial
A trailing zero comes from a factor of 10, which is a 2 paired with a 5. Among
1, 2, ... , p there are always more factors of 2 than of 5, so the fives are the bottleneck
and the answer is simply how many factors of 5 the product carries:
zeros(p) = p/5 + p/25 + p/125 + p/625 + ... + p/(largest power of 5 at most p)
using integer division and stopping when the divisor passes p. The term p/25 is there
because 25, 50, 75 each contribute a SECOND five; p/125 picks up the third, and so on.
Counting only p/5 is the classic wrong version and it is correct for every p below 25,
which is exactly why it survives a casual test.
## Why zeros is monotone
Every term is non-decreasing in p, so the sum is. Going from p to p + 1 adds the number of
fives in p + 1, which is never negative.
## This is NOT a kth-smallest problem, and the difference is the lesson
Everywhere else in this block the value returned by the lower-bound search is guaranteed to
occur in the data, because the count rises by one at a time. Here it does not: zeros jumps by
2 at p = 25, by 3 at p = 125, and by more at higher powers of 5. So some k are never hit:
zeros(20) = 4 zeros(25) = 6 nothing gives 5
The search still finds the smallest p with zeros(p) >= k, which is the right candidate and
the only candidate. What it cannot do is promise a hit, so the final step is a check:
if zeros(lo) == k: answer lo
else: answer -1
Leaving that check out returns 25 when asked for 5, which is a plausible-looking wrong answer.
## The bounds
lo = 1 and hi = 5k. Since zeros(5k) >= 5k/5 = k, the answer is never above 5k, and the
bound is tight enough that no wasted step matters.
## The boundary that breaks a careless implementation
Building the divisor as 5, 25, 125, ... by repeated multiplication overflows if the loop
condition is checked after the multiply rather than before. With p up to 5 * 10^9 the
divisor climbs to 5^14, which is about 6.1 * 10^9, and one more multiplication takes it to
3 * 10^10. That still fits in 64 bits, but the same loop written in 32 bits wraps to a
negative divisor and the sum runs away. Loop while divisor <= p.
## Relationship with problem 784
784 is the counterpart where the final check is unnecessary. Its count is also a sum of integer divisions and it also stops at the smallest argument reaching the target, but its count rises by exactly one as each member of its list is passed, so the stopping value is always a genuine answer.
zeros has no such property and the search itself cannot tell the difference. The lower bound is
still the only candidate worth testing, and the -1 case exists precisely because a candidate
and a hit stop being the same thing the moment a counter is allowed to step by more than one.
## Overflow
hi = 5k reaches 5 * 10^9 and the answer reaches 4 * 10^9. Both are past 2^31 - 1.
## Cost
Time O(log k * log p). Space O(1).
Constraints - `1 ≤ k ≤ 10^9`
Input
The first line contains a single integer k, the required number of trailing zeros.
Output
Print a single integer: the smallest p whose factorial ends in exactly k zeros, or -1 when no such p exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.