Factorial Zeros

16.5 Factorial Zeros: Write an algorithm which computes the number of trailing zeros in n factorial.

• I was thinking of using dynamic programming with factorial recursion. The issue is storing 32 bit numbers, which factorial can exceed very quickly.

• The better approach would be split up the factorial into its components, and find its prime factors. Any pair of 10, (5 and 2, as building blocks) should move us on to the next base. Therefore the solution would be min(num(5's), num(2's)). Since there will always be more 2's than 5's we can just count the 5's.

int trailing_zeros(int factorial) {
    if (factorial == 0) return -1;
    int count = 0;
    int temp;
    for (int i = 1; i <= factorial; i++) {
        temp = i;
        while (temp % 5 == 0) {
            count++;
            temp = temp / 5;
        }
    }
    return count;
}

int main()
{
    cout << trailing_zeros(13) << endl;
    cout << trailing_zeros(100) << endl;
    cout << trailing_zeros(932093) << endl;
}