Skip to main content

172. Factorial Trailing Zeroes

medium

Count the trailing zeros in n! without computing the factorial. A tiny recursion problem that's really a number-theory exercise — count the factors of 5.

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.

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

Trailing zeros come from factors of 10 = 2 * 5. There are always more 2s than 5s in n!, so count 5s.

Hint 2

n / 5 = count of multiples of 5 up to n. But 25, 125, ... each contribute extra factors of 5.

Hint 3

Total 5s = floor(n / 5) + floor(n / 25) + floor(n / 125) + ...

Hint 4

Recursive form: trailing(n) = n / 5 + trailing(n / 5). Iterative: divide n by 5 in a loop and accumulate.

Solution approach

Reveal approach

Count the factors of 5 in n! — they pair with the (always more abundant) factors of 2 to form trailing zeros. Recursive: trailing(n) = (n / 5) + trailing(n / 5), base case trailing(0) = 0. Iterative: count = 0; while n > 0: n /= 5; count += n. Both run in O(log_5 n) time and O(1) space (iterative) or O(log n) recursion stack. The intuition: multiples of 5 contribute one 5 each, multiples of 25 contribute one EXTRA 5, multiples of 125 contribute yet another, and so on. Sum these floor divisions to get the total exponent of 5 in n!.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • recursion
  • math
  • number-theory

Related problems

Asked at

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

  • Microsoft
  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →