Description
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Examples:
Example 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Example 3:
Input: n = 0
Output: 0Solution in Python
To solve the problem of counting the number of trailing zeroes inn! (the factorial of n), we need to understand how trailing zeroes are formed. Trailing zeroes are created by the factors of 10 in the number. Since 10 is the product of 2 and 5, we need to count the pairs of these factors in the factorial.
However, in any factorial, there are generally more factors of 2 than factors of 5. Therefore, 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 factors of 5, we can use the following approach:
- Count the number of multiples of 5 in the numbers from 1 to n.
- Count the number of multiples of 52=25 (since each contributes an additional factor of 5).
- Count the number of multiples of 53=125, and so on, until 5k where 5k≤n.
This method ensures that we count all the factors of 5 contributed by numbers like 25, 125, etc., which have more than one factor of 5.
class Solution:
def trailingZeroes(self, n: int) -> int:
# Initialize the count of trailing zeroes to 0
count = 0
# We start with the smallest power of 5 (i.e., 5)
power_of_5 = 5
# Loop until the power of 5 is less than or equal to n
while n >= power_of_5:
# Add the number of multiples of the current power of 5 to the count
count += n // power_of_5
# Move to the next power of 5
power_of_5 *= 5
# Return the total count of trailing zeroes
return countDetailed Comments in Code
- Initialize the count of trailing zeroes to 0: This variable will keep track of the total number of trailing zeroes in n!.
- We start with the smallest power of 5 (i.e., 5): The smallest power of 5 that we need to consider is 5 itself.
- Loop until the power of 5 is less than or equal to n: We will keep increasing the power of 5 until it exceeds nnn.
- Add the number of multiples of the current power of 5 to the count: The integer division
n // power_of_5gives the count of multiples of the current power of 5 in the range from 1 to n. - Move to the next power of 5: We multiply the current power of 5 by 5 to get the next higher power.
- Return the total count of trailing zeroes: Once the loop is complete, the count will contain the total number of trailing zeroes in n!.
This approach ensures that the solution runs in logarithmic time complexity with respect to nnn, specifically O(log5n).
Solution in Javascript
/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function(n) {
// Initialize the count of trailing zeroes to 0
let count = 0;
// We start with the smallest power of 5 (i.e., 5)
let power_of_5 = 5;
// Loop until the power of 5 is less than or equal to n
while (n >= power_of_5) {
// Add the number of multiples of the current power of 5 to the count
count += Math.floor(n / power_of_5);
// Move to the next power of 5
power_of_5 *= 5;
}
// Return the total count of trailing zeroes
return count;
};Solution in Java
class Solution {
public int trailingZeroes(int n) {
// Initialize the count of trailing zeroes to 0
int count = 0;
// We start with the smallest power of 5 (i.e., 5)
int power_of_5 = 5;
// Loop until the power of 5 is less than or equal to n
while (n >= power_of_5) {
// Add the number of multiples of the current power of 5 to the count
count += n / power_of_5;
// Move to the next power of 5
power_of_5 *= 5;
}
// Return the total count of trailing zeroes
return count;
}
}Solution in C#
public class Solution {
public int TrailingZeroes(int n) {
// Initialize the count of trailing zeroes to 0
int count = 0;
// We start with the smallest power of 5 (i.e., 5)
int power_of_5 = 5;
// Loop until the power of 5 is less than or equal to n
while (n >= power_of_5) {
// Add the number of multiples of the current power of 5 to the count
count += n / power_of_5;
// Move to the next power of 5
power_of_5 *= 5;
}
// Return the total count of trailing zeroes
return count;
}
}