[LeetCode] Factorial Trailing Zeros
Well, to compute the number of trailing zeros, we need to first think clear about what will generate a trailing 0
? Obviously, a number multiplied by 10
will have a trailing 0
added to it. So we only need to find out how many 10
's will appear in the expression of the factorial. Since 10 = 2 * 5
and there are a bunch more 2
's (each even number will contribute at least one 2
), we only need to count the number of 5
's.
Now let's see what numbers will contribute a 5
. Well, simply the multiples of 5
, like 5, 10, 15, 20, 25, 35, ...
. So is the result simply n / 5
? Well, not that easy. Notice that some numbers may contribute more than one 5
, like 25 = 5 * 5
. Well, what numbers will contribute more than one 5
? Ok, you may notice that only multiples of the power of 5
will contribute more than one 5
. For example, multiples of 25
will contribute at least two 5
's.
Well, how to count them all? If you try some examples, you may finally get the result, which is n / 5 + n / 25 + n / 125 + ...
. The idea behind this expression is: all the multiples of 5
will contribute one 5
, the multiples of 25
will contribute one more 5
and the multiples of 125
will contribute another one more 5
... and so on. Now, we can write down the following code, which is pretty short.
class Solution {
public:
int trailingZeroes(int n) {
int count = ;
for (long long i = ; n / i; i *= )
count += n / i;
return count;
}
};
最新文章
- sqlservr (708) 打开日志文件 C:\Windows\system32\LogFiles\Sum\Api.log 时出现错误 -1032 (0xfffffbf8)
- vim 快捷键 以及技巧
- 【MyEcplise 插件】反编译插件jad
- Image Generator (Image Builder)
- UIButton 设置为圆形,并且使用图片(UIImage)当做背景
- 自己改写了一个图片局部放大的jquery插件页面里面的html代码少了,同一个页面可以调用多个
- SPOJ 8222 Substrings(后缀自动机)
- WPF DataGrid 增加";更新";模板列,根据行Row的选择而显示";更新";按钮
- android性能优化的一些东西
- Python当前文件路径与文件夹删除操作
- 以C语言为例的程序性能优化 --《深入理解计算机系统》第五章读书笔记
- Angular 自定义指令传参
- 启动Mysql数据库报错误:-bash: ./start.sh: Permission denied
- C++ STL 顺序容器--list + 关联容器
- 修改CentOS的IP地址
- Python3入门(一)——概述与环境安装
- jsp页面如何读取从后台传来的json
- StreamSets 多线程 Pipelines
- Redis集群部署(redis + cluster + sentinel)
- vue 拦截器
热门文章
- css hacks
- 关于Go语言daemon启动的方法.
- Paper Reading 1 - Playing Atari with Deep Reinforcement Learning
- PadLeft函数
- atitit.LimeSurvey 安装 attilax 总结
- 操作XmlDocument时,出现";System.OutOfMemoryException";异常,如何解决加载大数据的情况?
- Swift培训
- 线程池 (thread pool) 的类型与实现方式
- LNMP笔记:php-fpm – 启动参数及重要配置详解
- python网络编程学习笔记(10):webpy框架