首页 > 代码库 > Factorial Trailing Zeroes
Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
最初想法是计算里面能被5整除的数字的个数(因为能被2整除的肯定多于5). 后来发现不对,要将所有数字包含的最大5的阶乘数加起来。 (即25的话要算2)
n!后缀0的个数 = n!质因子中5的个数 = floor(n/5) + floor(n/25) + floor(n/125) + ....
1 public class Solution { 2 public int trailingZeroes(int n) { 3 int result = 0; 4 // for(int i = 1; i <= n; i ++){ 5 // int cur = i; 6 // while(cur % 5 == 0){ 7 // cur /= 5; 8 // result ++; 9 // }10 // }11 for(long i = 5; i <= n; i *=5){12 result += (int)n / i;13 }14 return result;15 }16 }
Factorial Trailing Zeroes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。