Problem 44071. Smallest n, for n! to have m trailing zero digits

Created by Jihye Sofia Seo

Solve Later

For given positive integer n, its factorial often has many trailing zeros, in other words many factors of 10s. In order for n! to have at least "m" trailing zeros, what is the smallest "n" ?

Example: factorial(10) = 3628800 factorial(9) = 362880 In order to have 2 trailing zeros on factorial, the smallest n is 10.

Optional: Can you make an efficient algorithm for a very large m?

Solve

Solution Stats

42 Solutions
14 Solvers

Last Solution submitted on Mar 08, 2020

Last 200 Solutions

Solution Comments

Solution 1135219

1 Comment

1 Comment

yurenchu on 7 Mar 2017

I think this is (so far) the most efficient solution for large m. It requires at most log(4*m)/log(5) iterations; while the smaller sized solutions that have been suggested require at least 0.8*m iterations (or a very large array). For example, for m = 10^5, this solution takes at most 8 iterations while the other solutions of smaller size require at least 80,000 iterations.

Problem Recent Solvers14

Problem Tags

factorial factorisation integer power of primes

Problem 44071. Smallest n, for n! to have m trailing zero digits

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers14

Suggested Problems

More from this Author9

Problem Tags

Problem 44071. Smallest n, for n! to have m trailing zero digits

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers14

Suggested Problems

More from this Author9

Problem Tags

Players