172. Factorial Trailing Zeroes

Problem Statement

link: LeetCode.cn LeetCode Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1.

Example:

Input: n = 3 Output: 0

Input: n = 5 Output: 1

Input: n = 0 Output: 0

Solution Approach

To find the number of trailing zeroes in n!, count how many multiples of 5 are there up to n.

Algorithm

Certainly! Here are three key points for finding the number of trailing zeroes in n!:

1. Understanding Trailing Zeroes: Trailing zeroes in n! are formed by factors of 10, which are produced by pairs of factors 2 and 5. However, in factorials, there are always more factors of 2 than 5, so the count of trailing zeroes is determined by the number of times 5 is a factor in numbers from 1 to n.

2. Counting Multiples of 5: To find out how many trailing zeroes n! has, count how many multiples of 5 exist up to n. Each multiple contributes at least one factor of 5 to the factorial sequence, which correlates directly with the number of trailing zeroes.

3. Iterative Approach: Start with ans initialized to 0. Iterate through multiples of 5 (5, 10, 15, ...) up to n, counting how many times each multiple contributes a factor of 5 by continuously dividing by 5 until the quotient is no longer divisible by 5. Sum these counts to get the total number of trailing zeroes in n!.

Implement

    class Solution:
        def trailingZeroes(self, n: int) -> int:
            ans = 0
            while n != 0:
                n //= 5
                ans += n
            return ans

    //java code
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5) {
                ++ans;
            }
        }
        return ans;
    }
}        

    

Twitter  facebook  Email