algoadvance

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

Clarifying Questions

  1. What is the value range of n?
    • Typically, n can be any non-negative integer within a reasonable limit, let’s assume constraints of 0 <= n <= 10^4.
  2. What is a trailing zero?
    • A trailing zero is a zero at the end of a number, i.e., an integer like 100 has two trailing zeroes.

Strategy

To determine the number of trailing zeroes in the factorial of n (denoted as n!), we need to consider the factors that contribute to trailing zeroes. Trailing zeroes are produced by the factor 10, which is the product of 2 and 5. In a factorial, the number of 2s will always be more than or equal to the number of 5s, hence the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to n.

To count the number of trailing zeroes, we:

  1. Count the multiples of 5.
  2. Count the multiples of 25 (this accounts for numbers like 25, 50, etc., which contribute an extra factor of 5).
  3. Count the multiples of 125, 625, and so on.

In general, we keep dividing n by 5, 25, 125, etc., summing up the counts until n divided by the increasing powers of 5 is 0.

Code

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

Explanation

  1. Initialize count to 0: This variable will accumulate the number of trailing zeroes.
  2. Initialize power_of_5 to 5: This is the base factor we start dividing n by.
  3. While n is greater than or equal to power_of_5:
    • Add the integer division result of n // power_of_5 to count.
    • Multiply power_of_5 by 5 to consider the next power of 5.
  4. Return count: This gives the total number of trailing zeroes in n!.

Time Complexity

The time complexity of this solution is O(log_5(n)) because we repeatedly divide n by increasing powers of 5. This is efficient and suitable for the given constraints.

This concludes the solution for counting trailing zeroes in the factorial of an integer n.

Try our interview co-pilot at AlgoAdvance.com