LeetCode-172 Factorial Trailing Zeroes

题目描述

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

题目大意

给定一个正整数n，计算n！的后缀有几个零。

示例

E1

Input: 3
Output: 0

E2

Input: 5
Output: 1

解题思路

因为在n！中每出现一个5就会产生一个零（5 * 2 = 10、15 * 12 = 180、...），同时每出现一个25 = 5 * 5也会多出现一个零（注意，该多出来的零是之前计算的5出现的零之外的零），以此类推，每一个125 = 5 * 5 * 5也会多产生一个零。

复杂度分析

时间复杂度：O(log(n))

空间复杂度：O(1)

代码

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        //计算保存5、25、125、...产生的零的个数
        for(long long i = 5; n / i > 0; i *= 5) {
            ans += (n / i);
        }
        
        return ans;
    }
};