Factorial Trailing Zeroes - Practice Coding Problems

Factorial Trailing Zeroes - Problem

Math Medium

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Follow up: Could you write a solution that works in logarithmic time complexity?

Input & Output

Example 1 — Small Factorial

$ Input: n = 3

› Output: 0

💡 Note: 3! = 6, which has no trailing zeros

Example 2 — One Trailing Zero

$ Input: n = 5

› Output: 1

💡 Note: 5! = 120, which has 1 trailing zero (from 2×5=10)

Example 3 — Multiple Zeros

$ Input: n = 25

› Output: 6

💡 Note: 25! has 6 trailing zeros from factors: 5 multiples of 5 plus 1 extra from 25=5×5

Constraints

0 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n representing factorial

Process

Count factors of 5 in n!

Output

Number of trailing zeros

Key Takeaway

🎯 Key Insight: Trailing zeros come from pairs of factors 2 and 5, with 5s being the limiting factor

Asked in

M Microsoft 35 a Amazon 28 🍎 Apple 22 G Google 18

The key insight is that trailing zeros come from factors of 10, which are created by pairs of 2 and 5. Since there are always more factors of 2 than 5 in n!, we only need to count factors of 5. Best approach is the mathematical method counting multiples of 5, 25, 125, etc. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Approach - Count Factors of 5	O(log n)	O(1)	Count how many times 5 divides into n! without calculating factorial
Brute Force - Calculate Factorial	O(n)	O(1)	Calculate n! directly and count trailing zeros

Mathematical Approach - Count Factors of 5 — Algorithm Steps

Count multiples of 5: n/5
Count multiples of 25: n/25 (extra 5s)
Count multiples of 125: n/125 (more extra 5s)
Sum all counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Multiples of 5

Count numbers divisible by 5

Extra 5s

Count additional 5s from 25, 125, etc.

Sum

Total count gives trailing zeros

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    if (n < 0) return 0;
    
    int count = 0;
    long long powerOf5 = 5;
    
    // Count factors of 5, 25, 125, etc.
    while (powerOf5 <= n) {
        count += n / powerOf5;
        powerOf5 *= 5;
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Divide by powers of 5 until quotient becomes 0, takes log₅(n) iterations

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for counter variable

✓ Linear Space

85.0K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Approach - Count Factors of 5 — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler