LeetCode 172 Factorial Trailing Zeroes

Tag: 数学类题目 LeetCode Posted on 2022-02-22 21:28:12 Edited on 2022-02-22 21:36:12 Views: 134

概述

https://leetcode.com/problems/factorial-trailing-zeroes/

Could you write a solution that works in logarithmic time complexity?

解法

0 只能来自于 2 * 5,所以我们统计一下可以把 n! 分解出多少个 2 与 5 就能算出结果。

显然 2 的个数要多于 5 的个数,所以问题转换为 1~n 里有多少个 5 的倍数

不是啦,是转换成 1~n 里能分解出多少个 5。

答案是,int(n/5) + int(n/5^2) + ... int(n/5^m)

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        int c = n;
        while (c / 5 != 0) {
            count += c / 5;
            c /= 5;
        }
        return count;
    }
};

时间复杂度 O(logn)

未经允许,禁止转载,本文源站链接:https://iamazing.cn/