Number of trailing zeroes in factorial n (n!)


Write a function to calculate the number of trailing zeroes in factorial n (n!)


Possible Solution:
0 s are contributed due to multiplication of 2 and 5 in any factorial. Till 4! = 24, there are no 0 s. 5! = 120 has one. So we need to find out the number of 2 and 5 coming in a factorial. To count the number of pairs, we just have to count the number of multiple of 5’s.
5 contributes to one multiple of 10,
25 contributes two (because 25 = 5*5) and so on.
So the formula is:
Number of zeroes = n/5 + n/(5^2) + n/(5^3) + ….
Code:
1
2
3
4
5
6
7
8
9
int numOfTrailingZeroes(int num)
{
  int count = 0;
  for(int i = 5; num/i > 0; i *= 5)
  {
    count += num/i; 
  }
  return count;
}

0 comments:

Post a Comment