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

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

问题

给定一个整数 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种算法实现,以下是这个案例的输出结果:

3

分析:

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

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3854

发表评论

登录后才能评论