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)
1function trailingZeroes(n) {
2 let count = 0;
3 while (n > 0) {
4 n = Math.floor(n / 5);
5 count += n;
6 }
7 return count;
8}
9
10console.log(trailingZeroes(5));This JavaScript function follows the same logic, using a loop to calculate the trailing zeroes by counting the multiples of 5.
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 Java solution uses a nested loop structure to incrementally add to the total count based on divisibility by 5 for each integer in the range.