Code Implementation

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

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
};
      

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
}
      

var trailingZeroes = function(n) {
    let count = 0;
    while (n > 0) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
};
      

Problem Description

The "Factorial Trailing Zeroes" problem asks: Given an integer n, return the number of trailing zeroes in n! (that is, the factorial of n).

Constraints:

• Only one valid answer exists for each input.
• You are not required to actually compute the full factorial (as it gets huge fast).
• Input: a single integer n (0 ≤ n ≤ 10⁴ or higher).
• Output: the count of trailing zeroes in n!.

Thought Process

At first glance, you might think to compute the factorial of n and count the number of zeroes at the end. However, factorials grow extremely quickly, and even for moderate values of n, the result will not fit in standard data types. Therefore, a brute-force approach of calculating n! directly is not feasible.

Next, think about what causes trailing zeroes in a number: each trailing zero comes from a factor of 10, which is the product of 2 and 5. In factorials, there are usually more factors of 2 than 5, so the number of trailing zeroes is determined by the number of times 5 appears as a factor in the numbers from 1 to n.

The key insight is to count how many times 5 is a factor in all numbers from 1 to n. This is much more efficient than calculating the factorial itself.

Solution Approach

To count the number of trailing zeroes in n!, follow these steps:

1. Count the multiples of 5: Every multiple of 5 contributes at least one factor of 5 to the product. For example, numbers like 5, 10, 15, etc.
2. Account for higher powers of 5: Numbers like 25, 125, etc., contribute more than one factor of 5 (since 25 = 5 × 5, 125 = 5 × 5 × 5). For each such number, count all extra 5s.
3. Implementation:
   • Initialize a counter to zero.
   • While n is greater than zero:
     • Divide n by 5 (integer division) and add the result to the counter.
     • Update n to n // 5.
   • Repeat until n becomes zero.

Example Walkthrough

Let's take n = 30 as an example.

Step 1: Count how many multiples of 5 are ≤ 30.

• 30 // 5 = 6 (multiples: 5, 10, 15, 20, 25, 30)

• 30 // 25 = 1 (multiples: 25)

• 30 // 125 = 0

Time and Space Complexity

Brute-force approach:

• Computing the factorial directly is O(n), but storing the result is impractical for large n due to exponential growth.
• Counting trailing zeroes after computing the factorial is O(log n) (for scanning digits), but the calculation itself is the bottleneck.

• The loop divides n by 5 each time, so it runs O(log₅ n) times.
• Each iteration is O(1), so total time complexity is O(log n).
• Space complexity is O(1), as we only use a few integer variables.

Summary

The key insight to solving the "Factorial Trailing Zeroes" problem is understanding that trailing zeroes are formed from pairs of factors 2 and 5, and that factors of 2 are always more abundant than factors of 5 in a factorial. By counting the total number of times 5 appears in the prime factorization of all numbers from 1 to n, including higher powers, we can efficiently determine the number of trailing zeroes in n! without ever computing the factorial itself. This makes the solution both elegant and highly efficient.