Given an integer n, write a function that returns count of trailing zeroes in n!. Examples :
Input: n = 5 Output: 1 Factorial of 5 is 120 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
Trailing 0s in n! = Count of 5s in prime factors of n!
= floor(n/5) + floor(n/25) + floor(n/125) + ....
PHP
<?php// PHP program to count // trailing 0s in n!// Function to return trailing // 0s in factorial of nfunction findTrailingZeros( $n){ // Initialize result $count = 0; // Keep dividing n by powers // of 5 and update count for ($i = 5; $n / $i >= 1; $i *= 5) $count += $n / $i; return $count;}// Driver Code$n = 100;echo "Count of trailing 0s in ", 100, "! is ", findTrailingZeros($n);// This code is contributed by vt_m?> |
Output:
Count of trailing 0s in 100! is 24
Time Complexity: O(log5n)
Auxiliary Space: O(1)
Please refer complete article on Count trailing zeroes in factorial of a number for more details!
