C#LeetCode刷题之#172-阶乘后的零（Factorial Trailing Zeroes）

.Net中文网 • 2020年06月08日 19:44 • LeetCode • 阅读 1024

问题

给定一个整数 n，返回 n! 结果尾数中零的数量。

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

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

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

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

Note: Your solution should be in logarithmic time complexity.

示例

public class Program {

    public static void Main(string[] args) {
        var n = 18;

        var res = TrailingZeroes(n);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int TrailingZeroes(int n) {
        //统计包含因子5的数量即可
        var res = 0;
        while(n > 1) {
            res += (n /= 5);
        }
        return res;
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

分析：

显而易见，以上算法的时间复杂度为： $O(log_{5}n)$ 。