Friday, July 18, 2014

Number of trailing zeros in a factorial

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/

Reactions:

0 comments:

Post a Comment