LeetCode 172.Factorial Trailing Zeroes (阶乘后的零)

墨蓝 2022-04-15 00:14 182阅读 0赞

题目描述：

给定一个整数 *n*，返回 *n*! 结果尾数中零的数量。

**示例 1:**

输入: 3
    输出: 0
    解释: 3! = 6, 尾数中没有零。

**示例 2:**

输入: 5
    输出: 1
    解释: 5! = 120, 尾数中有 1 个零.

**说明:** 你算法的时间复杂度应为 *O*(log *n*)。

解题思路：

这个想法是：

0来自10。  
10来自2 x 5  
我们需要考虑5和2的所有产生。例如4×5 = 20 ...  
因此，如果我们将5的所有数字作为一个因子，我们有足够多的偶数与它们配对以获得10

例一

1到23之间有多少5的倍数？有5,10,15和20，四个倍数为5.与偶数因子中的2配对，这使得四个因子为10，所以：23！有4个零。

例二

从1到100的数字中有多少个5的倍数？

因为100÷5 = 20，所以，在1和100之间有20×5。

但等等，实际上25是5×5，所以25的每个倍数都有5的额外因子，25×4 = 100，这引入了额外的零。

那么，我们需要知道有多少25在1~100之间？由于100÷25 = 4，因此在1和100之间存在四个25的倍数。

最后，我们在100中得到20 + 4 = 24个尾随零！

上面的例子告诉我们，我们需要关心5,5×5,5×5×5,5×5×5×5 ....

例三

由给定的数字4617。

5 ^ 1：4617÷5 = 923.4，所以得到923个因子5

5 ^ 2：4617÷25 = 184.68，因此我们得到184个附加因子5

5 ^ 3：4617÷125 = 36.936，所以我们得到36个额外因子5

5 ^ 4：4617÷625 = 7.3872，因此我们得到7个额外因子5

5 ^ 5：4617÷3125 = 1.47744，所以我们得到1个因子5

5 ^ 6：4617÷15625 = 0.295488，小于1，所以停在这里。

那么4617！有923 + 184 + 36 + 7 + 1 = 1151尾随零。

AC C++ Solution:

class Solution {
    public:
        int trailingZeroes(int n) {
            int cnt = 0;
            for(long long i = 5; i <= n; i*=5) {
                cnt += (n/i);
            }
            
            return cnt;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

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

相关阅读

相关 LeetCode - Easy - 172. Factorial Trailing Zeroes

Topic Math Description [https://leetcode.com/problems/factorial-trailing-zeroe

今天药忘吃喽~/ 2022年12月29日 12:51/ 0 赞/ 165 阅读

相关 LeetCode--172. Factorial Trailing Zeroes

Problem: > Given an integer n, return the number of trailing zeroes in n!. > > Note: Y

清疚/ 2022年08月21日 00:01/ 0 赞/ 150 阅读

相关 172. Factorial Trailing Zeroes （计算n的阶乘尾部有多少个零）

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution sho

r囧r小猫/ 2022年07月15日 01:21/ 0 赞/ 184 阅读

相关 172. Factorial Trailing Zeroes （计算n的阶乘尾部有多少个零）

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution sho

红太狼/ 2022年07月15日 01:21/ 0 赞/ 188 阅读

相关 LeetCode172—Factorial Trailing Zeroes

原题 [原题链接][Link 1] > Given an integer n, return the number of trailing zeroes in n!.

逃离我推掉我的手/ 2022年07月14日 01:47/ 0 赞/ 313 阅读

相关 [leetcode]: 172. Factorial Trailing Zeroes

1.题目 Given an integer n, return the number of trailing zeroes in n!. Note: Your sol

超、凢脫俗/ 2022年06月15日 07:55/ 0 赞/ 199 阅读

相关 leetcode 172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution sho

深藏阁楼爱情的钟/ 2022年06月08日 07:28/ 0 赞/ 169 阅读

相关 LeetCode172. 阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。示例 2:

╰半夏微凉°/ 2022年05月23日 02:16/ 0 赞/ 188 阅读

相关 LeetCode 172.Factorial Trailing Zeroes (阶乘后的零)

题目描述：给定一个整数 n，返回 n! 结果尾数中零的数量。示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。示例

墨蓝/ 2022年04月15日 00:14/ 0 赞/ 183 阅读

相关【LeetCode】 172. 阶乘后的零

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

爱被打了一巴掌/ 2021年06月10日 20:38/ 0 赞/ 380 阅读