Sponsored
Sponsored
To determine the number of trailing zeroes in a factorial (n!), observe that trailing zeroes are produced by 10s in the factorization of n!. Each 10 is the product of a 2 and a 5. In most factorial numbers, there are more factors of 2 than 5. Therefore, the number of trailing zeroes is determined by the number of times 5 is a factor. We count the number of multiples of 5 in the numbers from 1 to n (because each contributes at least one factor of 5). Then, we count the multiples of 25, 125, 625, etc., as these contribute an extra factor of 5 each time. Continue this counting until the power of 5 exceeds n.
Time Complexity: O(log5 n)
Space Complexity: O(1)
1def trailingZeroes(n):
2 count = 0
3 while n > 0:
4 n //= 5
5 count += n
6 return count
7
8print(trailingZeroes(5))This Python function iteratively reduces n by dividing it by 5 and incrementing a counter by the result of the division.
In this approach, we directly count the number of trailing zeroes by iterating over all the numbers up to n, checking if each is divisible by 5. If so, we increment a counter to track the factors of 5. This approach isn't as efficient as counting the most significant power of 5 due to potentially higher iteration counts.
Time Complexity: O(n log5 n)
Space Complexity: O(1)
1
This C implementation iterates over numbers from 1 to n. For each number, if it is divisible by 5, it divides it further, counting each division as a factor of 5.