September 11, 2010
Factorial Trailing Zeros
Problem
Given a positive integer. Find the number of trailing zeros in the integer’s factorial. For example the factorial of 10 is 3628800 so the algorithm should print 2
Solution
Let us start by a simple example. Factorial of 5 = 5 x 4 x 3 x 2 = 5 x 2 x 2 x 3 x 2 = 10 x 12 = 120. As you can see each pair of 5 x 2 contributes one zero in the final result. The problem reduces to finding the number of 5 x 2 pairs. Please refer to the code below for more details.
Code
Here is the code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
//Includes #include <iostream> //STD using namespace std; //Receives integer number as input int TrailingZeros(int n) { //Number of times 5 is a factor int fc = 0; //Number of times 2 is a factor int tc = 0; //A factorial is computed as the multiplication //of the number with all numbers before it so //we need to examine all of them for (int i = 1; i <= n; i++) { int num = i; //As long as the number can be //divided by 5 keep incrementing //the 5 counter while (num%5 == 0) { num = num/5; fc++; } //Once the number can no longer be divided //by 5 start checking if it can be divided //by 2 then keep incrementing the 2 counter while (num%2 == 0) { num = num/2; tc++; } } //Once the above loop is finished then we //have already determined the 5 and 2 factors //of the factorial. Each multiplication of 5 x 2 //contributes one trailing zero in the final result if (tc == fc || tc < fc) { return tc; } else { return fc; } } //Main function void main() { //Print number of factorial trailing //zeros for numbers between 1 and 20 for (int i = 0; i <= 20; i++) { cout << i << " : " << TrailingZeros(i) << endl; } } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco