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 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.

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

More Recursion practice problems

See all Recursion problems →