Counting Trailing Zeros in Factorials

The number of trailing zeros in a factorial comes from counting how many times 5 appears as a factor in the numbers from 1 to n.

Factors of 2 always outnumber factors of 5 in any factorial. So the zeros come from pairs of 2 and 5. Since we have more 2s than 5s we just need to count the 5s.

To count the 5s we look at multiples of 5. But some numbers like 25 contain more than one 5. So we divide n by 5 to get the count of multiples of 5. Then we divide by 25 to count extra 5s in numbers like 25 and 50. We keep going with 125 625 and so on.

This gives us a recursive solution:

int trailingZeroes(int n) {
    if (n == 0) return 0;
    return n/5 + trailingZeroes(n/5);
}

The function calls itself with n divided by 5 each time. It stops when n becomes 0.

#recursion #math