Factorial Trailing Zeroes

medium math

Problem

Given an integer n, return the number of trailing zeroes in n!.

Inputn = 100

Output24

A trailing zero comes from a factor of 10 = 2 · 5. There are always more 2s than 5s in 1·2·…·n, so just count the 5s: ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

def trailing_zeroes(n):
    count = 0
    while n > 0:
        n //= 5
        count += n
    return count

function trailingZeroes(n) {
  let count = 0;
  while (n > 0) {
    n = Math.floor(n / 5);
    count += n;
  }
  return count;
}

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

Explanation

A trailing zero appears whenever a number is divisible by 10, and 10 = 2 × 5. So the number of trailing zeros in n! is the number of pairs of 2 and 5 hiding in the product 1·2·…·n. Since 2s are far more common than 5s, the count is decided entirely by how many factors of 5 there are.

So we just count the 5s. Multiples of 5 contribute one each, multiples of 25 contribute an extra one, multiples of 125 yet another, and so on. The total is ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

The loop computes this neatly: repeatedly do n //= 5 and add the new n to count. The first division gives multiples of 5, the second gives multiples of 25 (the deeper factor), and it stops when n reaches 0.

Example: n = 100. 100 // 5 = 20, then 20 // 5 = 4, then 4 // 5 = 0. Adding the terms: 20 + 4 = 24, so 100! ends in 24 zeros.

Because we divide by 5 each round, only a handful of steps are needed even for huge n, making this very fast.

Time: O(log₅ n) Space: O(1)