172. Factorial Trailing Zeroes

Medium

Problem Description

Given an integer n, return the number of trailing zeroes in n!.

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

Examples

Example 1:
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:
Input: n = 0
Output: 0
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def trailingZeroes(n: int) -> int:
    count = 0
    i = 5
    
    while i <= n:
        count += n // i
        i *= 5
    
    return count

Java Solution


class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        
        for (long i = 5; i <= n; i *= 5) {
            count += n / i;
        }
        
        return count;
    }
}

C++ Solution


class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        
        for (long i = 5; i <= n; i *= 5) {
            count += n / i;
        }
        
        return count;
    }
};

JavaScript Solution


/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    let count = 0;
    
    for (let i = 5; i <= n; i *= 5) {
        count += Math.floor(n / i);
    }
    
    return count;
};

C# Solution


public class Solution {
    public int TrailingZeroes(int n) {
        int count = 0;
        
        for (long i = 5; i <= n; i *= 5) {
            count += n / (int)i;
        }
        
        return count;
    }
}

Complexity Analysis

Solution Explanation

This solution counts factors of 5:

Key points: