[leetcode]: 172. Factorial Trailing Zeroes

超、凢脫俗 2022-06-15 07:55 297阅读 0赞

1.题目

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
求n!末尾有多少个0。要求O(logn)复杂度

2.分析

末尾的0有2*5或10贡献
1*2*3*4…*n-1*n
总体来说就是看有多少个5,5k
5,10,15,20,25,30,…
由于25有两个5，所以还要找25k
25,50,75…
以此类推
125k

3.代码

  1. int trailingZeroes(int n) {
  2.     int count = 0;
  3.     while (n) {
  4.         n = n / 5;
  5.         count += n;
  6.     }
  7.     return count;
  8. }
  10. int trailingZeroes(int n) {
  11.     return n==0?0:n/5+trailingZeroes(n/5);
  12. }

发表评论

表情：
评论列表 （有 0 条评论，297人围观）

还没有评论，来说两句吧...

相关阅读