面试题 16.05. 阶乘尾数

image.png

对于n!的结果，其有多少个尾随0取决了1-n这n个数字中不断拆分有多少对2和5,以10为例， 10=2*5 还有单独的数字2和5 所以是两队2和5，因此10！有2个尾随0，而2的个数肯定比5多，因此只要找出有多少个5即有多少对2和5 （像25就可以得到2个5）

  1. class Solution {
  2.     public int trailingZeroes(int n) {
  3.         int cnt=0;
  4.         long num=5;
  5.         while(n/num>0)
  6.         {
  7.             cnt+=n/num;
  8.             num*=5;
  9.         }
  10.         return cnt;
  11.         // 25/5=5  25/25=1  5+1=6个  5（1个5） 10（1个5） 15（1个5） 20（1个5） 25（2个5）
  13.     }
  14. }
  15. //O(logn)
  16. //O(1)