Factorial Trailing Zeroes

Medium
156.

Factorial Trailing Zeroes

Factorial Trailing Zeroes is a medium coding problem on math, asked in Amazon, Google, Infosys and Bloomberg interviews.

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n × (n - 1) × (n - 2) × … × 2 × 1.

Example 1

Input
n = 3
Output
0
Explanation
3! = 6, which ends in no zero.

Example 2

Input
n = 5
Output
1
Explanation
5! = 120, one trailing zero.

Example 3

Input
n = 30
Output
7

Constraints

  • 0 <= n <= 100000

Follow-up: Can you do it in logarithmic time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Factorial Trailing Zeroes — Solution in Python, Java & C++

Factorial Trailing Zeroes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math.

Factorial Trailing Zeroes is a medium coding problem on math, asked in Amazon, Google, Infosys and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Math
  • Asked at: Amazon, Google, Infosys, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n × (n - 1) × (n - 2) × … × 2 × 1.

Example 1

Input: n = 3
Output: 0
Explanation: 3! = 6, which ends in no zero.

Example 2

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3

Input: n = 30
Output: 7

Constraints

  • 0 <= n <= 100000

Follow-up: Can you do it in logarithmic time?

Hints for Factorial Trailing Zeroes

  1. Hint 1

    A trailing zero comes from a factor of 10 = 2 × 5.

  2. Hint 2

    Factors of 2 are far more plentiful than factors of 5, so the answer is just the number of 5s in the factorisation of n!.

  3. Hint 3

    Count multiples of 5, then of 25, then of 125, … and add them up: 25 contributes two fives, not one.

How to solve Factorial Trailing Zeroes

Each trailing zero is a factor of 10 = 2 × 5, and factors of 2 are far more plentiful than factors of 5 in n!, so the count of zeros equals the number of times 5 divides n!.

Approach

  1. Start count = 0 and power = 5.
  2. While power <= n, add n // power to count and multiply power by 5.
  3. Return count.

Why it works

By Legendre's formula the exponent of a prime p in n! is ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …: the first term counts every multiple of p, the second adds the extra factor each multiple of p² carries, and so on. Since the exponent of 2 always exceeds that of 5, the 5s are the bottleneck.

Complexity

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

Pitfalls

  • Counting only multiples of 5 undercounts — 25! has six trailing zeros, not five.
  • Computing n! and stripping zeros overflows almost immediately.

Reference solution

Python

def trailingZeroes(n: int) -> int:
    count = 0
    power = 5
    while power <= n:
        count += n // power
        power *= 5
    return count

Java

public static int trailingZeroes(int n) {
    int count = 0;
    for (long power = 5; power <= n; power *= 5) {
        count += n / power;
    }
    return count;
}

C++

int trailingZeroes(int n) {
    int count = 0;
    for (long long power = 5; power <= n; power *= 5) {
        count += n / power;
    }
    return count;
}

JavaScript

var trailingZeroes = function(n) {
    let count = 0;
    for (let power = 5; power <= n; power *= 5) {
        count += Math.floor(n / power);
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue