#172

Medium

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Factorial Trailing Zeroes

Given a number n, find how many trailing zeroes are in n! using a math-driven approach.

Problem Statement

You are tasked with calculating how many trailing zeroes are in the factorial of a number n, denoted n!. A trailing zero is created whenever the number ends in a zero, and this occurs when n! contains factors of 10, which is the product of 2 and 5.

Given an integer n, return the number of trailing zeroes in n!. For example, 5! = 120, which ends in one trailing zero, while 3! = 6, which does not have any trailing zeros.

Examples

Example 1

Input: n = 3

Output: 0

3! = 6, no trailing zero.

Example 2

Input: n = 5

Output: 1

5! = 120, one trailing zero.

Example 3

Input: n = 0

Output: 0

Example details omitted.

Constraints

0 <= n <= 104

Solution Approach

Counting Factors of 5

The number of trailing zeroes is determined by how many times 5 is a factor in the numbers from 1 to n. For every multiple of 5, there is at least one factor of 5. The total number of trailing zeroes is the sum of the integer divisions of n by powers of 5, i.e., n // 5 + n // 25 + n // 125, and so on.

Efficient Calculation

This approach avoids calculating n! directly, which would be inefficient for large n. Instead, by counting the multiples of powers of 5, we calculate the number of factors of 5 present in n! and deduce the number of trailing zeroes.

Handling Edge Cases

Special edge cases include when n = 0, where n! is defined as 1, which has zero trailing zeroes. Also, n values lower than 5 don’t generate any trailing zeroes. Ensure that the edge cases are properly handled in the code.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(log n) since we are dividing n by increasing powers of 5. The space complexity is O(1), as we only need a few variables to store intermediate values.

What Interviewers Usually Probe

The candidate demonstrates an understanding of the mathematical properties of factorials.
The candidate can implement an efficient solution without calculating the entire factorial.
The candidate effectively handles edge cases such as n = 0.

Common Pitfalls or Variants

Common pitfalls

Brute force methods that attempt to calculate n! directly will fail for large values of n due to factorial growth.
Overlooking powers of 5 beyond the first (e.g., missing multiples of 25, 125).
Incorrect handling of n = 0, which should return 0 trailing zeroes.

Follow-up variants

Extend the problem to find trailing zeroes in large factorials where n exceeds typical data types.
Modify the problem to count trailing zeroes in base b factorials instead of base 10.
Optimize the approach further for very large n to minimize computational time.

FAQ

How can I solve the Factorial Trailing Zeroes problem efficiently?

The efficient approach is to count how many times 5 is a factor in the numbers from 1 to n by repeatedly dividing n by powers of 5.

What is the time complexity for the Factorial Trailing Zeroes problem?

The time complexity is O(log n), where n is the given integer, as the solution involves repeatedly dividing n by powers of 5.

What happens when n = 0 in the Factorial Trailing Zeroes problem?

When n = 0, n! is 1, which has zero trailing zeroes.

Are there any edge cases in this problem?

Yes, edge cases include when n = 0 or when n is less than 5, which results in no trailing zeroes.

What common mistakes should I avoid in the Factorial Trailing Zeroes problem?

Avoid directly computing n! as this is inefficient for large n, and make sure to count all powers of 5.

terminal

Solution

Solution 1: Mathematics

The problem is actually asking how many factors of $5$ are there in $[1,n]$.

1

2

3

4

5

6

7

class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans

Continue Practicing

#171 excel sheet column number #168 excel sheet column title #166 fraction to recurring decimal