[Leetcode] 172. Factorial Trailing Zeroes 解题报告

xiaoxiao2021-02-28  83

题目:

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

Note: Your solution should be in logarithmic time complexity.

思路:

这与其说是一道编程题目,不如说是一道数学题目。如果对一个数进行质因数分解就可以知道,它后面有多少个0取决于它的质因子里面包含多少个5。因此,我们的算法的目标就是计算n中包含多少个n。算法的时间复杂度是O(logn)。

代码:

class Solution { public:     int trailingZeroes(int n) {         int trail_zero_num = 0;     while (n >= 5) {        n /= 5;        trail_zero_num += n;     }     return trail_zero_num;     } };

转载请注明原文地址: https://www.6miu.com/read-78761.html

最新回复(0)