Problem
Write an algorithm which computes the number of trailing zeros in n factorial.
Solution
The trailing zeros are constructed by multiplying pairs of 2 and 5. So to count the number of trailing zeros, we need to count the number of pairs of 2 and 5. For a factorial, there are way more number of factor 2 than 5 so we just need to count the number of factor 5 in the factorial. The factor 5 is constructed by 5, 5^2, 5^3, etc. For example, there is only 1 factor 5 (5 itself) in 5! so there is only 1 trailing zero. There are 3 factor 5 (5, 10 and 15) in 15! so there are 3 trailing zeros. So, it boils down to number of 5's.Java code
public static int numZeros(int num) { int count = 0; if (num < 0) { System.out.println("Factorial is not defined for < 0"); return 0; } for (int i = 5; num / i > 0; i *= 5) { count += num / i; } return count; }
References
http://tianrunhe.wordpress.com/2012/05/14/number-of-trailing-zeros-in-a-factorial/
0 comments:
Post a Comment