Count trailing zeroes in factorial

Given an integer n, we have to returns count of trailing zeroes in n! .

Examples :

Input: n = 5
Output: 1
Explanation: Factorial of 5 is 120 which has one trailing 0.
Input: n = 10
Output: 2
Explanation: Factorial of 10 is 3628800 which have 2 trailing zeroes.

Try it on GfG Practice

Table of Content

[Naive Approach] By calculating the factorial - O(n) Time and O(1) Space
[Expected Approach] Repeated division by 5 - O(log n base 5) Time and O(1) Space

[Naive Approach] By calculating the factorial - O(n) Time and O(1) Space

The idea is to calculate the factorial of the number and then count the number of trailing zeros by repeatedly dividing the factorial by 10 till the last digit is 0. The number of times the factorial is divided by 10 is the number of trailing zeros. This approach is not useful for large numbers as calculating their factorial will cause overflow.

C++

#include <iostream>
using namespace std;

// Function to calculate
// factorial of a number
int factorial(int n) {
    int fact = 1;
    for (int i = 1; i <= n; ++i) {
        fact *= i;
    }
    return fact;
}

// Function to count trailing
// zeros in factorial
int trailingZeroes(int n) {
    int fact = factorial(n);
    int count = 0;

    // Count trailing zeros by
    // dividing the factorial by 10
    while (fact % 10 == 0) {
        count++;
        fact /= 10;
    }

    return count;
}

int main() {
    int n = 10;
    cout << trailingZeroes(n) << endl; 
    return 0;
}

Java

public class Main {

    // Function to calculate 
    // factorial of a number
    public static int factorial(int n) {
        int fact = 1;
        for (int i = 1; i <= n; ++i) {
            fact *= i;
        }
        return fact;
    }

    // Function to count trailing 
    // zeros in factorial
    public static int trailingZeroes(int n) {
        int fact = factorial(n);
        int count = 0;

        // Count trailing zeros by 
        // dividing the factorial by 10
        while (fact % 10 == 0) {
            count++;
            fact /= 10;
        }

        return count;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(trailingZeroes(n));  
    }
}

Python

# Function to calculate
# factorial of a number
def factorial(n):
    fact = 1
    for i in range(1, n + 1):
        fact *= i
    return fact

# Function to count trailing
# zeros in factorial
def trailingZeroes(n):
    fact = factorial(n)
    count = 0

    # Count trailing zeros by 
    # dividing the factorial by 10
    while fact % 10 == 0:
        count += 1
        fact //= 10

    return count

if __name__ == "__main__":
    n = 10
    print(trailingZeroes(n))

using System;
class Program {

    // Function to calculate 
    // factorial of a number
    public static int Factorial(int n) {
        int fact = 1;
        for (int i = 1; i <= n; ++i) {
            fact *= i;
        }
        return fact;
    }

    // Function to count trailing
    // zeros in factorial
    public static int trailingZeroes(int n) {
        int fact = Factorial(n);
        int count = 0;

        // Count trailing zeros by 
        // dividing the factorial by 10
        while (fact % 10 == 0) {
            count++;
            fact /= 10;
        }

        return count;
    }

    static void Main() {
        int n = 10;
        Console.WriteLine(trailingZeroes(n)); 
    }
}

JavaScript

// Function to calculate
// factorial of a number
function factorial(n)
{
    let fact = 1;
    for (let i = 1; i <= n; ++i) {
        fact *= i;
    }
    return fact;
}

// Function to count trailing
// zeros in factorial
function trailingZeroes(n)
{
    let fact = factorial(n);
    let count = 0;

    // Count trailing zeros by
    // dividing the factorial by 10
    while (fact % 10 === 0) {
        count++;
        fact /= 10;
    }

    return count;
}

// Driver code
const n = 10;
console.log(trailingZeroes(n));

Output

[Expected Approach] Repeated division by 5 - O(log n base 5) Time and O(1) Space

The idea is to consider all prime factors of factorial n. A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s in n!, our task is done.

How does this work? A trailing 0 is formed by multiplication of 5 and 2. So if we consider all prime factors of all numbers from 1 to n, there would be more 2s than 5s. So the number of 0s is limited by number of 5s. If we count number of 5s in prime factors, we get the result. Consider the following examples:

n = 5: There is one 5 and three 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So a count of trailing 0s is min(1, 3) = 1.
n = 11: There are two 5s and eight 2s in prime factors of 11! (2 ⁸ * 3⁴ * 5² * 7). So the count of trailing 0s is min(2, 8) = 2.

We can observe that the number of 2s in prime factors is always more than or equal to the number of 5s. So, if we count 5s in prime factors, we are done.

How to count the total number of 5s in prime factors of n! ?

A simple way is to calculate floor(n/5). For example, 7! has one 5, 10! has two 5s. But, numbers like 25, 125, etc have more than 5 instead of floor (n / 5). For example, if we consider 28! we get one extra 5 and the number of 0s becomes 6. Handling this is simple, first, divide n by 5 and remove all single 5s, then divide by 25 to remove extra 5s, and so on.

Following is the summarized formula for counting trailing 0s:

Trailing 0s in n! = Count of 5s in prime factors of n! = floor(n/5) + floor(n/25) + floor(n/125) + ..

C++

#include <iostream>
using namespace std;

int trailingZeroes(int n)
{
    // Edge Case
    if (n < 0)
        return -1;

    // Initialize result
    int count = 0;

    // Keep dividing n by powers of
    // 5 and update count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}

int main()
{
    int n = 10;
    cout <<trailingZeroes(n);
    return 0;
}

#include <stdio.h>

int trailingZeroes(int n)
{
    // Edge Case
    if (n < 0)
        return -1;

    // Initialize result
    int count = 0;

    // Keep dividing n by powers of
    // 5 and update count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}

int main()
{
    int n = 10;
    printf("%d\n", trailingZeroes(n));
    return 0;
}