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)
1public class FactorialTrailingZeroes {
2 public int trailingZeroes(int n) {
3 int count = 0;
4 while (n > 0) {
5 n /= 5;
6 count += n;
7 }
8 return count;
9 }
10
11 public static void main(String[] args) {
12 FactorialTrailingZeroes sol = new FactorialTrailingZeroes();
13 int n = 5;
14 System.out.println(sol.trailingZeroes(n));
15 }
16}The solution in Java repeats division by 5 until n becomes zero, accumulating the quotient each time. This provides 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
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.