Finding the Number of Trailing Zero's in Factorial of a Number

Factorial of a number is one of the most basic sums that you'll be doing whenever you learn a programming language. Finding the number of trailing zero's in the factorial of a number sounds pretty simple right ? You can just find the factorial of the number and you can run a while loop until factorial % 10 == 0 and increment a counter.

But it doesn't work like that. There is no data type in C which can hold the factorial of 21 or greater. So you cannot simply find the factorial and find the number of zero's. The solution for the problem is pretty simple. You can just find the number of two's and number of five's (5 x 2 = 10) in every number that constitutes the factorial and return the number of five's. That's it. Sounds very simple right ? Yes it is.

Program


  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4.   
  5. int zeros(int A){  
  6.     int two = 0;  
  7.     int five = 0;  
  8.     int temp;  
  9.       
  10.     for(int i = 2; i <= A; i++){  
  11.         temp = i;  
  12.         while(temp % 2 == 0 || temp % 5 == 0){  
  13.             if(temp % 2 == 0){  
  14.                 two++;  
  15.                 temp = temp / 2;  
  16.             }  
  17.             if(temp % 5 == 0){  
  18.                 five++;  
  19.                 temp = temp / 5;  
  20.             }  
  21.         }  
  22.     }  
  23.       
  24.     return ((two > five) ? five : two);  
  25. }  
  26.   
  27. int main(int argc, const char * argv[]) {  
  28.     cout<<zeros(100);  
  29.     return 0;  
  30. }  

Feel free to post your doubts below :)

Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming