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)
1#include <stdio.h>
2
3int trailingZeroes(int n) {
4 int count = 0;
5 while (n > 0) {
6 n /= 5;
7 count += n;
8 }
9 return count;
10}
11
12int main() {
13 int n = 5;
14 printf("%d\n", trailingZeroes(n));
15 return 0;
16}The function trailingZeroes calculates the number of trailing zeroes in the factorial of a given number n. It repeatedly divides n by 5, adding the quotient to count, which represents the number of trailing zeroes.
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#include <iostream>
using namespace std;
int trailingZeroes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 5 == 0 && num > 0) {
count++;
num /= 5;
}
}
return count;
}
int main() {
int n = 5;
cout << trailingZeroes(n) << endl;
return 0;
}This C++ function goes over every integer between 1 and n and divides by 5 to find the count of factors of 5, adding to the count.