Problem 39.5 · Math for Coding InterviewsMedium

Factorial Trailing Zeroes

What it teaches: Count factors of 5 instead of computing n!.

Practise it on judges as “Factorial Trailing Zeroes”.

In plain words

Every zero at the end of a number comes from a 10, and 10 = 2 × 5. In n! there are always more 2s than 5s, so just count the 5s: one from every multiple of 5, one more from every multiple of 25, and so on.

Return the number of trailing zeros of n!. Example: n = 5 → 1 (5! = 120).

The problem

Return the number of trailing zeros in n!.

Example 1

Input: n = 5
Output: 1

5! = 120.

Constraints

0 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Zeros at the end of a huge product

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int trailingZeroes(int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 3	0
2	n = 5	1
3	n = 0	0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Count fives · O(log₅ n)

Count fives

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

while n > 0: n /= 5; count += n.

▶ Dry run: Count the factors of 5n = 5

vars(vars)

n: 5count: 0

Step 1/35! = 1 × 2 × 3 × 4 × 5 = 120. Zeros need a 5 paired with a 2.

Approach 1

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

Verdict: No big numbers.

Before you submit

Edge cases and common mistakes

Test these inputs

n < 5 (0)
n = 25 (6: 25 contributes two fives)

Mistakes people make

Counting only multiples of 5 once.

Interview

Follow-up questions

How many n have exactly k trailing zeros?

Command Palette

The problem

Approaches

Count fives

Edge cases and common mistakes

Follow-up questions