Number of trailing zeros in factorial#123

Number of trailing zeros in factorial (Editorial)

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

⌊ \frac{n}{5} ⌋ + ⌊ \frac{n}{5 ^{2}} ⌋ + ⌊ \frac{n}{5 ^{3}} ⌋ + ...

\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + ...

The summation continues until the next term equals $0$ .

Example

Find the number of zeros at the end of $100!$

⌊ \frac{100}{5} ⌋ + ⌊ \frac{100}{5 ^{2}} ⌋ + ⌊ \frac{100}{5 ^{3}} ⌋ + ... = 20 + 4 = 24

\left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{5^2} \right\rfloor + \left\lfloor \frac{100}{5^3} \right\rfloor + ... = 20 + 4 = 24

The third term is already equal to zero, since $100 < 5^{3} = 125$ 100 < 5^3 = 125.

Algorithm implementation

Read the value of $n$ .

scanf("%d",&n);

Compute the result $r es$ 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();
  }
}

Java

Python implementation

Read the value of $n$ .

n = int(input())

Compute the result $r es$ 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)