Home » Algorithms

Find trailing zeros in factorial of a number

Here, we are going to learn how to find/count number of trailing zeros in a factorial of a number?
Submitted by Radib Kar, on November 14, 2018

Problem statement:

Find the number of trailing zeros in n! (Where, n is the given input).

Solution:

Computing a factorial is of course expansive. Though using dynamic programming the computing expanse can be managed, for the large value of n, the factorial value is going exceed normal data size. Needless to say, computing the whole factorial is not the way to find the number of trailing zeros. There must be some advanced algorithm to find the no of trailing zeros.

Firstly, we need to understand what causes trailing zeroes. A pair of 2 & 5 is the reason behind a trailing zero. Thus a pair of 2 & 5 in the factorial expression leads to a trailing zero. Thus we simply need to check how many pairs (different) of 2 & 5 are there.

Let's say 5!
5!= 5*4*3*2*1 (thus only one pair)
5!=120 ( only one trailing zero)

Intuition says that we don’t even need to find the number of pairs as the occurrence of 2 as a factor is obvious if a 5 is present as a factor. Thus we only need to check how many 5 is there as a factor in the factorial.

Algorithm:

    Set count to 0
    For(i=5;n/i>0;i=i*5)
        count=count+ n/i;
    Return count

C++ code to find trailing zeros in factorial of a number

#include<bits/stdc++.h>
using namespace std;

int trailingZeros(int n){
	int count=0;

	if(n<0)
		return -1;
	for(int i=5;n/i>0;i*=5){
		count+=n/i;
	}

	return count;
}

int main(){
	int n;

	cout<<"enter input,n"<<endl;
	cin>>n;

	if(trailingZeros(n))
		cout<<"no of trailing zero in "<<n<<"! is "<<trailingZeros(n)<<endl;
	else
		cout<<"input is negative, can't proceed"<<endl;
	
	return 0;
}	

Output

First run:
enter input,n
15 
no of trailing zero in 15! is 3

Second run:
enter input,n
100
no of trailing zero in 100! is 24