CodingGyan

Trailing Zeros of n!

easy Math and Number Theory

Problem

Print how many zeros n! (n factorial) has at its end. n can be very large, so do not compute the factorial.

Constraints

  • 0 <= n <= 10^15

Examples

Input

100

Output

24

Solutions

Best approachTime O(log n)Space O(1)

n! has about n * log(n) digits, so computing it is impossible for big n. Counting factors of 5 with repeated division is O(log n).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : The number of zeros.
 * Approach: Count the factor 5.
 * Time    : O(log n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: Each zero comes from one factor 10 = 2 * 5. There are always more 2s than 5s, so we count the 5s.
        // Step 2: Multiples of 5 give one 5, multiples of 25 give one more, multiples of 125 one more, and so on.
        long count = 0;
        long divisor = n;
        while (divisor > 0) {
            divisor /= 5;
            count += divisor;
        }
        return count;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. Why do we count only the factor 5?

Try these next