这篇文章上次修改于 5 个月前,可能其部分内容已经发生变化,如有疑问可询问作者。
阶乘尾随零的个数
题目描述
简要说明
就是找出 n! 尾部的零的个数。
思路
我开始是想算出来在去找零的个数,后来证实是不行的,一是到最后数字太多导致溢出了,而是超出了时间复杂度的限制。
结果一波摸索,发现 LeetCode 上的题大多都是考验的是对数学思维的理解,问题的转化。找出尾部的零其实就是找有多少个 10 相乘,一个 10 相乘就多一个 0,10 是有
2 * 5
得出的,有一个 5 的同时必定前面出现一个 2,所以就是找有多少个 5。 2n * 5n => 10n
(n 为系数), 例如 25 2*5
有一个 10.同时 25 中又有两个 5。所以 25 其实不止一个 5,他有两个 5.由此得出,想知道 x 中有几个五其实就是(x 为待阶层数), x / 5 + x / 5 / 5 + x / 5 / 5 .... 直到 x / 5 ^ m 等于 0 ( / 为整除)例如:
5
==> 1 * 2 * 3 * 4 * 5
=> 120
=> 一个0
25
==> 1 * 2 * 3 * ... 25
=> 25 / 5 => 25 = 5 * 5 => 六个0实现
注意使用
Math.floor
向下取整文章标题:
文章作者:
文章链接: [复制]
最后修改时间:
商业转载请联系站长获得授权,非商业转载请注明本文出处及文章链接,未经站长允许不得对文章文字内容进行修改演绎。
本文采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
亲亲留个评论再走呗
正在加载评论区...