172. Factorial Trailing Zeroes

Description

The function calculates the number of trailing zeroes in the factorial of a given number ( n ). Trailing zeroes are formed by factors of 10 in the number, and each 10 is the result of multiplying 2 and 5. Since there are usually more factors of 2 than factors of 5 in a factorial, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to ( n ).

Intuition

To determine the number of trailing zeroes in ( n! ) (the factorial of ( n )), we need to count how many times 10 divides into ( n! ). Since 10 is made up of the prime factors 2 and 5, and there are typically more factors of 2 than 5, the number of trailing zeroes is determined by the number of times 5 is a factor. This is because every factor of 5 can pair with a factor of 2 to form a trailing zero.

Approach

1. Initialize a counter for the number of trailing zeroes.
2. Iterate through powers of 5. For each power of 5, count how many numbers up to \( n \) are divisible by that power.
3. Sum these counts to get the total number of factors of 5 in \( n! \).
4. Return this sum as it represents the number of trailing zeroes in \( n! \).

Complexity

Time Complexity:

( O(\log_5 n) ), as the number of iterations depends on the number of times 5 can be multiplied before exceeding ( n ).

Space Complexity:

( O(1) ), as the space used does not depend on the size of ( n ) but only on a few variables.

Code

C++

class Solution {
public:
    int trailingZeroes(int n) {
        int fives = 0;
        for (int i = 5; i <= n; i *= 5) {
            fives += n / i;
        }
        return fives;
    }
};

Python

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

Java

class Solution {
    public int trailingZeroes(int n) {
        int fives = 0;
        for (int i = 5; i <= n; i *= 5) {
            fives += n / i;
        }
        return fives;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
    let fives = 0;
    for (let i = 5; i <= n; i *= 5) {
        fives += Math.floor(n / i)
        console.log(n, i)
    }
    return fives;
};