Easy · Count Powers of Five
Understand → Visualise → Practice.
Return the number of trailing decimal zeroes in n factorial without constructing the factorial.
Each trailing zero needs a factor 10 = 2 × 5. Factorials have plenty of 2s, so count the 5s: n/5 + n/25 + n/125 + …
Add ⌊n / 5⌋: numbers with at least one factor 5.
Keep dividing n by 5 and adding, which counts 25, 125, … extra times.
Stop when the quotient is 0.
O(log₅ n) time and O(1) space.
Computing n! directly overflows quickly and is slow.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.