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;
    }

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

As we need to count the number of trailing zeroes we can say a trailing zero comes when a number is multiplied by 10, right?

So if we have a number num = 123

when it is multiplied by 10 it becomes 1230 (number of trailing zeros = 1), if we again multiply that number by 10 then it becomes 12300 (number of trailing zeros = 2).

So we can conclude that the number of trailing zeros is the number of times it is multiplied by 10.

So the number 10 forms when 5 is multiplied by 2 i.e. 10 = 5*2, we need to check how many pairs of 5 and 2 we can find to form 10’s.

In a number line, we can see that the multiple of the number 2 occurs after every alternate integer, and the multiple of the number 5 occurs after every 4 numbers.

I.e. if we have numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.

Multiple of 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20. (10 times).

Multiple of 5: 5, 10, 15, 20. (4 times).

So we can say that if we represent a number in its prime factor, it can be represented as 

num =  5^x * 2^y * a1^b1 * a2^b2 * a3^b3 * …..an^bn.

where x,y,b1,b2 ….bn are the exponents of the prime factors(2,5,a1,a2 ….an) respectively.

Here if we closely observe, we can observe that for any number n, we can see that x<y (x is the exponent raised to 5 and y is the exponent raised to 2).

So if we take the minimum of x and y, let's say z so the z number of times we can form the number 10.

i.e. min(x,y) = z , 5^z * 2^z = (5*2)^z = 10^z. As x<y. 

The number z comes from the integer x(which is the power of 5).

So the number of trailing zeros in a number n is equal to n/5 + n/5² + n/5³ + ...

Now let us understand with an example where n=24, so the number of occurrences of 5 in the prime factorization of  24! is 4.

In 24! Only a multiple of 5 will contribute to the count of 5, so each number 5, 10, 15, 20 will contribute to the count of 5 i.e. count = 4.

General formula , n/5

Now let's check for n = 25, so if we solve it the formula that we have derived above n/5 = 25/5 = 5.

But is it correct?

In 25!, according to the formula (n/5), each number 5, 10, 15, 20, and 25 will contribute 1 to the count but we can see it’s incorrect because we can write 25 as 5*5 so it will contribute 2 to the count.

So if we divide n/5 it will give us a count of 5 for each of the multiples of 5 i.e.(5,10,15,20,25) and when we divide it by 5^2 i.e. 25 it will give us the count of 1 for each multiple of 25 i.e. (25).

I.e. in total 1+1+1+1+2=6.

Now if we take another example 126 here the multiple of 126! Which will contribute to the count of 5 are

5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60….125.

Where a multiple of 5 will contribute 1 to the count,

Similarly multiple of 5^2 = 25 i.e. 25,50,75,100,125 will contribute 2 to the count.

Similarly multiple of 5^3 = 125  i.e. 125 will contribute 3 to the count.

So in general if we want to find the count of 5 which occurs prime factorization of n! equal to 

n! / (5^1) + n! / (5^2) +  n! / (5^3) + ….0(till n!/(5^z) <=0 ).

Since we get the count of 5 from here it can form multiple 10 by multiplying it with an efficient number of 2.

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 number of divisions needed is proportional to the number of powers of 5 less than or equal to n. 

The largest power of 5 less than n is 5^k, where 5k≤n. Solving 5k≤n gives k≈log⁡5(n). 

Therefore, the number of operations is O(log⁡5n), which is effectively O(logn).

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.