Skip to main content

Math Basics

Find the Number of Trailing Zeroes in a Given Factorial of n

Examples : 

Input: 5
Output: 1
Explanation: A factorial of 5 is 120, so it had only 1 trailing zero. 

Input: 10
Output: 2
Explanation: A factorial of 5 is 3628800, so it had only 2 trailing zeros. 

💡
Try it yourself first!

Intuition

The brute force approach to this question is to find the factorial of the number and then count the number of trailing zeroes by repeatedly dividing it by 10 until we get a non-zero number in the ones place.

Brute Force Approach

To implement the brute force solution, first, we need to find the factorial of a number and then repeatedly divide it to count the number of zeroes.

For the small value of n where n! is less than equal to 1e18, the integer can fit in a 64-bit integer but for larger values, it can’t fit and will give us integer overflow.

So to avoid this integer overflow, we have to think up a different approach.

Dry Run

Input: n = 5

  • User enters 5.

Factorial Calculation:

  • Initialize fact = 1.
  • Loop runs from 2 to n (5):
    • fact = 1 × 2 = 2
    • fact = 2 × 3 = 6
    • fact = 6 × 4 = 24
    • fact = 24 × 5 = 120
  • Final factorial value: 120.

Counting Trailing Zeros:

  • Initialize count = 0.
  • While num % 10 == 0, increase count and divide num:
    • 120 % 10 == 0 → count = 1, num = 120 / 10 = 12.
    • 12 % 10 != 0, so loop stops.

Output:

  • The number 120 has 1 trailing zero, so the output is 1.

Time Complexity- O(n)

The brute force approach involves calculating the factorial of n by multiplying all numbers from 1 to n, which takes O(n) time. After computing the factorial, we count the trailing zero's by repeatedly dividing it by 10, which takes O(log n) time in the worst case. However, since computing the factorial dominates, the overall time complexity remains O(n).

Space Complexity - O(1)

The factorial calculation uses a single variable to store the result, making the space complexity O(1). Since we are not using any extra space except for some static variables to store the answer, and static variables are not included in space complexity, the overall space complexity remains O(1).

Code Implementation
C++ Code Try on Compiler! 
// Function to calculate factorial
long long factorial(int n) {
    long long fact = 1;
    for (int i = 2; i <= n; i++) {
        fact *= i;
    }
    return fact;
}

// Function to count trailing zeros in factorial
int countTrailingZeros(long long num) {
    int count = 0;
    while (num % 10 == 0) {
        count++;
        num /= 10;
    }
    return count;
}

Java Code Try on Compiler! 
public static long factorial(int n) {
        long fact = 1;
        for (int i = 2; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }

    public static int countTrailingZeros(long num) {
        int count = 0;
        while (num % 10 == 0) {
            count++;
            num /= 10;
        }
        return count;
    }

Python Code Try on Compiler! 
def factorial(n):
    fact = 1
    for i in range(2, n + 1):
        fact *= i
    return fact

def count_trailing_zeros(num):
    count = 0
    while num % 10 == 0:
        count += 1
        num //= 10
    return count

Javascript Code Try on Compiler! 
function factorial(n) {
        let fact = 1n; // Use BigInt to prevent overflow
        for (let i = 2n; i <= BigInt(n); i++) {
            fact *= i;
        }
        return fact;
    }

    function countTrailingZeros(num) {
        let count = 0;
        while (num % 10n === 0n) {
            count++;
            num /= 10n;
        }
        return count;
    }
The brute force code works for small numbers but causes overflow for larger values since factorial grows exponentially.
The brute-force approach fails because storing n! value in an integer leads to overflow.

Optimized Solution

Intuition

Trailing zeroes in a factorial come from factors of 10, which are formed by pairing 2s and 5s. Since multiples of 2 are more frequent, the number of trailing zeroes is determined by the count of 5s in the factorial’s prime factorization. We count how many times 5 appears as a factor in numbers up to n, including higher powers like 25, 125, etc.

Approach

let’s think in a reverse order
How does a number gets a trailing zero?

for eg:

  • n=9 (let’s add a trailing zero to 9)
  • n=n×10=90 (we multiplied by 10)
  • n=n×10=900

OBSERVATION: Hence multiplying by 10 everytime can cause a trailing zero.

Example n = 10;
10! = 1×2×3×4×5×6×7×8×9×10 = 3,628,800

Can you figure out how many 10 we can find?

  • 10 (first number from the right in the factorial)
  • 5 × 2 = 10 (this also forms a 10)

Conclusion:
As we can observe in the above explanation, If we count the number of pairs of 2 and 5 in the factorial representation, we can determine the number of 10s in the factorial and, hence, the number of trailing zeroes.

Do we need to calculate the number of 2s?
Consider n=10
10! = 1×2×3×4×5×6×7×8×9×10 = 3,628,800.

Prime Factorization of 10!:
Breaking it down into prime factors: 10!=(2^8)×(3^4)×(5^2)×7
Here, the number of 2s (8) is greater than the number of 5s (2).

Why do we only count 5s?

  • Every pair of 2 and 5 forms a 10, contributing to a trailing zero.
  • Since 5 appears fewer times than 2, each 5 can pair with only one 2 to form 10.
  • Thus, the number of trailing zeroes is determined by the count of 5s in the factorial factorization, not 2s.

Conclusion:
To find trailing zeroes in n!, we only need to count how many times 5 appears in the factorization, as it is the limiting factor in forming 10s.

How to count the number of 5s in n!?
To determine how many trailing zeros are in n!, we need to count how many times 5 appears in the multiplication.

Let’s take some examples:

Example 1: n = 10
10! = 1×2×3×4×5×6×7×8×9×10

Look at the numbers that contain 5:
5, 10 → Each of these contributes one factor of 5.
So, there are 2 trailing zeros in 10!.

Example 2: n = 25
25! = 1,2,3,…,24,25

Look at the numbers that contain 5:
5, 10, 15, 20, 25
Each of these contributes one factor of 5. But 25 itself is 5 × 5, meaning it contributes an extra factor of 5.

So, we count:
5, 10, 15, 20 → 1 factor each
25 → 2 factors (since 25 = 5 × 5)
Total: 6 trailing zeros.

Example 3: n=100
Look at the multiples of 5:

5, 10, 15, 20, ..., 95, 100 (Each contributes 1 factor of 5 → 20 factors)
25, 50, 75, 100 (Each contributes 1 extra factor because they are multiples of 25 → 4 extra factors)
Total trailing zeros = 20 + 4 = 24.

Key Observations:

  • Every multiple of 5 contributes one factor of 5.
  • Every multiple of 25 contributes one extra factor of 5.
  • Every multiple of 125 contributes one more, and so on.
Code Implementation
C++ Code Try on Compiler! 
// Function to find the number of trailing zeroes in n!
int countTrailingZeroes(int n) {
    // Initialize count of trailing zeroes
    int count = 0; 
    
    // Iterate through powers of 5
    for (int i = 5; n / i >= 1; i *= 5) {
    	// Add the count of multiples of the current power of 5
        count += n / i; 
    }
    // Return the total count of trailing zeroes
    return count; 
}

Java 
public class TrailingZeroes {
    // Function to count trailing zeroes in n!
    public static int countTrailingZeroes(int n) {
        int count = 0; // Initialize count
        for (int i = 5; n / i >= 1; i *= 5) {
            count += n / i; // Count multiples of current power of 5
        }
        return count; // Return total count
    }
}

Python 
# Function to count trailing zeroes in n!
def count_trailing_zeroes(n):
    count = 0  # Initialize count
    i = 5
    while n // i >= 1:
        count += n // i  # Count multiples of current power of 5
        i *= 5
    return count  # Return total count

Javascript 
// Function to count trailing zeroes in n!
function countTrailingZeroes(n) {
    let count = 0; // Initialize count
    for (let i = 5; Math.floor(n / i) >= 1; i *= 5) {
        count += Math.floor(n / i); // Count multiples of current power of 5
    }
    return count; // Return total count
}

Time Complexity : O(logn)

The time complexity is O(log₅ n) because we repeatedly divide n by powers of 5 (i.e., 5, 25, 125, etc.) until n becomes smaller than the current power of 5. Since the number of divisions grows logarithmically, the complexity is log base 5 of n.

Space Complexity : O(1)

The space complexity of this algorithm is O(1).
The algorithm uses a fixed amount of extra space regardless of the input size. It only requires a few variables (like the count, and loop counter), and the amount of memory needed does not grow with n.