文章目录

• 思路
• • 方法1
  • 方法2
• 代码
• • 方法1
  • 方法2

思路

方法1

末尾每一个0都能看做是一个10
0的数量就转换成n!=123*…n形成的10的数量
每一个10可以看作是25
10的数量就转换成形成25的数量
5的数量：
第零个5=05
第一个5=15
第二个5=25
第三个5=35
第四个5=45
第五个5=55
第六个5=55
……

2的数量：
等价于偶数数量
第0个5～第1个5之间存在偶数，于是存在2
第1个5～第2个5之间存在偶数，于是存在2
……

由此可得是要有一个5，那么就会存在至少一个2与之相匹配
于是有2*5的数量就转换成计算5的数量

方法2

序列0：1,2,3,4,5,6,7,8…<=n
序列1：5,10,15,20,25,30…5*m<=n
m=n/5

序列2：1,2,3,4,5,6,7,8…
序列3：5,10,15,20,25,30…5*m1<=m
m1=m/5

序列4：1,2,3,4,5,6,7,8…
序列5：5,10,15,20,25,30…5*m2<=m1
m2=m1/5
……
mi=m(i-1)/5
mi<5,停止迭代

m为1～n中能被5整除的数
m1为1～n中能被25整除的数
m2为1～n中能被125整除的数
……
于是5的数量=m+m1+…+m(i-1)

代码

方法1

int trailingZeroes(int n){int ret=0, temp;for(int i=0;i<=n;i+=5){temp=i;while(temp%5==0 && temp/5>0){ret++;temp=temp/5;}}return ret;
}

方法2

int trailingZeroes(int n){int ret=0;while(n>0){ret+=n/5;n/=5;}return ret;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！