Here you will learn about how to count trailing zeros in factorial of number.
One simple approach to count trailing zeros is first find factorial of number and then count the zeros in the factorial one by one. It is fine for smaller number like 10.
10! = 3628800
So, trailing zeros = 2
But what about big numbers like 100. The factorial of 100 has 24 zeros in the end and almost 160 digits. Its really hard to store that big number and then count the zeros one by one.
There is a simple and very fast method to do this. We can count the zeros by counting the 5s in prime factor of n factorial.
Trailing zeros in n! = Count 5s in prime factors of n! = floor(n/5) + floor(n/25) + floor(n/125) + . . . .
It is very frequently asked question in competitive programming. Let us see how this method can be implemented in C.
C Program to Count Trailing Zeros in Factorial of Number
#include<stdio.h>
int main(){
int i,n,count=0;
printf("Enter a number:");
scanf("%d",&n);
//repeatedly divide n by powers of 5 and update count
for(i=5;n/i>=1;i*=5){
count+=n/i;
}
printf("Trailing Zeroes=%d",count);
return 0;
}
Output
If you have any doubts regarding above tutorial then comment below.
Thanks for sharing!
Is there any reason why we divide by factors of 5 in each iteration?
Its just an algorithm, we have to follow it.
@Admin.- With all due respect , there is a reason for every algorithmic design that works 🙂 @Aufuray – Do keep in mind that 5 and 2 are the parents of 10 (i.e they literally give birth to 10 when multiplied together )
So, what we are basically doing in this algo , is that we are counting the number of fives that are being multiplied .. ( Wondering why we will not count the 2’s ? Because 2 ‘s will always be more than the number of 5’s needed to make a 10 .. but as 5 is the limiting determinant to make a 10 , therefore we count the number of 5’s)
More mathematical explanation –>http://mathworld.wolfram.com/Factorial.html
I’m impressed, I must say. Rarely do I come across a blog that’s both educative and interesting,
and without a doubt, you’ve hit the nail on the head.
The issue is something which too few people are speaking intelligently about.
I am very happy that I stumbled across this during my hunt for something relating to this.
Wow, Nice!
can u xplain about the logic
With all due respect , there is a reason for every algorithmic design that works 🙂 @ram – Do keep in mind that 5 and 2 are the parents of 10 (i.e they literally give birth to 10 when multiplied together )
So, what we are basically doing in this algo , is that we are counting the number of fives that are being multiplied .. ( Wondering why we will not count the 2’s ? Because 2 ‘s will always be more than the number of 5’s needed to make a 10 .. but as 5 is the limiting determinant to make a 10 , therefore we count the number of 5’s)
More mathematical explanation –>http://mathworld.wolfram.com/Factorial.html