Factorial Trailing Zeroes
Understanding the Problem
We need to count how many trailing zeroes appear at the end of n!. A trailing zero is a zero at the rightmost end of a number. For example, 120 has one trailing zero, and 1000 has three.
One option is to compute n! and then count the zeroes at the end. But factorials grow fast. 20! is already over 2 billion, and 100! has 158 digits, far beyond what a 64-bit integer holds. Computing the full factorial is impractical for large n, so we need a mathematical shortcut.
A trailing zero is produced by a factor of 10, and 10 = 2 x 5. The number of trailing zeroes equals the number of times 10 divides into n!, which equals the number of (2, 5) pairs in the prime factorization of n!. There are always more factors of 2 than 5 in a factorial (every even number contributes a 2, but only every fifth number contributes a 5), so the number of (2, 5) pairs is limited by the number of factors of 5. Counting trailing zeroes reduces to counting factors of 5 in n!.
Key Constraints:
0 <= n <= 10^4. With n up to 10,000, an O(n) scan over every number is fast enough. The follow-up asks for O(log n), which a direct formula achieves.ncan be 0. This is the edge case where 0! = 1, which has zero trailing zeroes. Both approaches below handle it without special casing, since their loops never execute when n is 0.
Approach 1: Brute Force (Count Factors of 5 for Each Number)
Intuition
The answer equals the total number of factors of 5 across the numbers 1 through n. We can find it directly: iterate through every number from 1 to n, count how many times 5 divides it, and sum those counts.
A number contributes more than one factor of 5 when it is divisible by a higher power of 5. In 10!, the numbers 5 and 10 each contribute one factor of 5, so the total is 2. In 25!, the number 25 contributes two factors (25 = 5 x 5), while 5, 10, 15, and 20 each contribute one, giving 6 total.
Algorithm
- Initialize a counter
count = 0. - For each number
ifrom 1 ton: - While
iis divisible by 5, divideiby 5 and incrementcount. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n log_5(n)). We iterate through n numbers, and for each number, the inner while loop runs at most log_5(n) times (since we keep dividing by 5).
- Space Complexity: O(1). Only a few integer variables are used.
This scans every number from 1 to n, even though four out of five are not divisible by 5 at all. The next approach counts the factors of 5 across the whole range with a few divisions, giving O(log n) time.
Approach 2: Optimal (Divide by Powers of 5)
Intuition
Instead of inspecting each number, we count all factors of 5 in n! at once by grouping numbers according to which power of 5 divides them.
- The count of numbers from 1 to n divisible by 5 is
floor(n/5). Each contributes at least one factor of 5. - The count divisible by 25 (= 5^2) is
floor(n/25). Each of these contributes a second factor of 5, which the first term has not yet counted. - The count divisible by 125 (= 5^3) is
floor(n/125). Each contributes a third factor. - Continue until the power of 5 exceeds n.
A number like 25 is counted once by the floor(n/5) term and once more by the floor(n/25) term, so its two factors of 5 are both accounted for. This layering is why each higher-power term adds exactly the extra factors the lower terms missed. The total is:
floor(n/5) + floor(n/25) + floor(n/125) + floor(n/625) + ...
This is Legendre's formula for the power of a prime p in n!, specialized to p = 5.
Every second number is even, so factors of 2 are always more abundant than factors of 5. The count of (2, 5) pairs is limited by the scarcer factor, which is always 5.
Algorithm
- Initialize
count = 0. - While
n >= 5: - Divide n by 5 (integer division).
- Add the result to
count. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(log_5(n)). We divide n by 5 in each iteration, so the loop runs log_5(n) times. For n = 10,000, that is about 6 iterations.
- Space Complexity: O(1). Only two integer variables are used.