Problem

Write an algorithm which computes the number of trailing zeros in n factorial.

OR

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

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Examples

Example 1

1
2
3

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2

1
2
3

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3

1
2

Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 10^4

Follow up

Could you write a solution that works in logarithmic time complexity?

Solution

n = 5: There is one 5 and 3 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So count of trailing 0s is 1. n = 11: There are two 5s and three 2s in prime factors of 11! (2^8 * 3^4 * 5^2 * 7). So count of trailing 0s is 2. eg. n = 11 i = 5, n/i = 2 => 2 > 0, i =25 count = 2 i = 25 n/i = 0, i = 125 count += 0 => count = 2

Method 1 – Count Factors of 5 (Efficient)

Intuition

Trailing zeros in n! are created by multiplying pairs of 2 and 5 in its prime factors (since 2 × 5 = 10, which adds a trailing zero). For every such pair, we get one trailing zero. However, in any factorial, there are always more factors of 2 than factors of 5, so the number of trailing zeros is determined by the number of times 5 appears in the factorization of n!.

To count the number of trailing zeros, we need to count the number of pairs of 2 and 5. Since 2s are abundant, we only need to count the number of 5s in the prime factors of n!.

But some numbers contribute more than one 5. For example, 25 contributes two 5s, 125 contributes three, and so on. So, for each power of 5 (5, 25, 125, …), we count how many multiples of that power are ≤ n and sum them up.

For example:

  • n = 5: There is one 5 and three 2s in the prime factors of 5! (2 × 2 × 2 × 3 × 5). So the count of trailing zeros is 1.
  • n = 11: There are two 5s and three 2s in the prime factors of 11! (2^8 × 3^4 × 5^2 × 7). So the count of trailing zeros is 2.

This leads to the formula:

Trailing zeros in n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

Approach

For each power of 5 (5, 25, 125, …), count how many multiples of that power are ≤ n. Sum these counts:

Trailing zeros in n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        for (long long i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        return count;
    }
};
1
2
3
4
5
6
7

func trailingZeroes(n int) int {
    count := 0
    for i := 5; n/i > 0; i *= 5 {
        count += n / i
    }
    return count
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (long i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun trailingZeroes(n: Int): Int {
        var count = 0
        var i = 5L
        while (n / i > 0) {
            count += (n / i).toInt()
            i *= 5
        }
        return count
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        i = 5
        while n // i > 0:
            count += n // i
            i *= 5
        return count
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn trailing_zeroes(n: i32) -> i32 {
        let mut count = 0;
        let mut i = 5;
        while n / i > 0 {
            count += n / i;
            i *= 5;
        }
        count
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    trailingZeroes(n: number): number {
        let count = 0;
        for (let i = 5; Math.floor(n / i) > 0; i *= 5) {
            count += Math.floor(n / i);
        }
        return count;
    }
}

Complexity

  • ⏰ Time complexity: O(log₅ n) — For each power of 5 (5, 25, 125, …), we divide n by that power. The number of such divisions is proportional to log base 5 of n, so the loop runs O(log₅ n) times.
  • 🧺 Space complexity: O(1) — We only use a constant amount of extra space (just a few integer variables), regardless of the input size.