
问题
给定一个整数 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
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3854。