Skip to main content

172. Factorial Trailing Zeroes

medium

Count the trailing zeroes of n! without computing n! itself. A classic number-theory problem that hinges on the observation that each trailing zero comes from a 2x5 pair — and fives are the bottleneck.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, return the number of trailing zeroes in n!. Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1. Follow up: Could you write a solution that works in logarithmic time complexity?

Constraints

  • 0 <= n <= 10^4

Examples

Example 1

Input
n = 3
Output
0

Explanation: 3! = 6, no trailing zero.

Example 2

Input
n = 5
Output
1

Explanation: 5! = 120, one trailing zero.

Example 3

Input
n = 0
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A trailing zero is produced by a factor of 10, which is a factor of 2 * 5. So count the number of 2-5 pairs in the factorization of n!.

Hint 2

There are always more 2s than 5s among the factors of 1, 2, ..., n. So the count of 5s is the limiting factor.

Hint 3

Count factors of 5 in 1..n: floor(n/5) numbers contribute at least one 5, floor(n/25) contribute an extra, floor(n/125) yet another, and so on.

Hint 4

Sum n/5 + n/25 + n/125 + ... until the term hits 0. That's the answer.

Solution approach

Reveal approach

Each trailing zero comes from a factor of 10 = 2*5 in n!. Two-factors are plentiful so fives are the bottleneck. Count the multiples of 5 in 1..n, then multiples of 25 (each contributes an extra 5), then 125, 625, and so on. The total is floor(n/5) + floor(n/25) + floor(n/125) + ... — a geometric-ish sum that terminates as soon as a term becomes 0. Implementation: start with divisor = 5 and loop while divisor <= n, adding n // divisor each iteration and multiplying divisor by 5. O(log5 n) time, O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More Math practice problems

See all Math problems →