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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Factorial Trailing Zeroes and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →