123. Number of zeroes in factorial
Find the number of zeros at the end of n! (n factorial).
Input. One integer n (1 ≤ n ≤ 2 * 109).
Output. Print the number of zeros at the end of n!
|
Sample input |
Sample output |
|
7 |
1 |
SOLUTION
mathematics
Algorithm analysis
The
factorial of an integer n is the
product of all positive integers from 1
to n. A zero at the end of the product appears as a result of
multiplying 2 and 5. However, in the prime factorization of n! there are more twos than fives. Therefore, the number of zeros at the end
of n! is equal to the number of fives in the factorization
of n!. The number of such
fives is
+ 
+ 
+ …
The
summation continues until the
next term equals 0.
Example
Find the number of zeros at
the end
of 100!
+ 
+ 
+ … = 20 + 4 = 24
The third term is already equal to
zero, since 100 < 53 = 125.
Algorithm
implementation
Read
the value of n.
scanf("%d",&n);
Compute
the result res using the formula.
res = 0;
while(n > 0)
{
n /= 5;
res += n;
}
Print the number of zeros at the end of n!
printf("%d\n",res);
Java implementation
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int res = 0;
while (n > 0)
{
n /= 5;
res += n;
}
System.out.println(res);
con.close();
}
}
Python implementation
Read
the value of n.
n = int(input())
Compute
the result res using the formula.
res = 0
while n > 0:
n = n // 5
res += n
Print the number of zeros at the end of n!
print(res)