首页 > 试题广场 >

阶乘末尾0的数量

[编程题]阶乘末尾0的数量
  • 热度指数：11761 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数 n ，返回 n! 结果的末尾为 0 的数量。

n! 是指自然数 n! 的阶乘,即 : 。
特殊的,  0 的阶乘是 1 。

数据范围： 
进阶：空间复杂度 ，时间复杂度
复杂度要求：
不大于
示例1

输入

3

输出

0

说明

3!=6
示例2

输入

5

输出

1

说明

5!=120
示例3

输入

1000000000

输出

249999998
算法知识视频讲解
添加回答
牛客402776921号头像 牛客402776921号
我愿称数论题为最难的类型，我实在无法去思考这么多数能有这么多规律。
发表于 2021-05-30 20:54:12 回复(0)
别卷啦！头像 别卷啦！
终于知道js咋没人了 200000000000000000 这个测试用例过不去
发表于 2021-01-19 18:55:35 回复(3)
Go
奋斗的习习张头像 奋斗的习习张 
package main

/**
 * the number of 0
 * @param n long长整型 the number
 * @return long长整型
*/
func thenumberof0( n int64 ) int64 {
    // write code here
    var res int64
    res = 0
    for n > 0 {
        n /= 5
        res += n
    }
    return res
}

发表于 2021-07-17 16:57:41 回复(0)
Java
惠灵顿靖头像 惠灵顿靖
观察一下10以内的数字互相乘，会发现，只有





相乘会产生0，而且 ，...
所以我们只需要看一下 以内 能拆出多少对
然后我们可以发现，有5因子的数比有2因子的数要少，所以我们就看能拆出来多少5就可以了，因为肯定能有足够数量的因子2来匹配。

所以阶乘末尾0的数量就是 中能拆出来的5的数量。但是，从 1 遍历到 n 每个数看一下它能除多少次 5 是不行的。因为 n 的数据范围是1e18。遍历1e18个数复杂度太大了。
那我们来考虑一下，5的倍数可以至少产生1个5，25的倍数可以产生至少2个5，125的倍数可以产生至少3个5...
这样的话 中有n/5个5的倍数，n/25个25的倍数，n/125个125的倍数...

所以答案就是 n/5+n/25+n/25.. 
    public long thenumberof0 (long n) {
        // write code here
       // if(n==0)return 1;
        long count=0;
        while(n!=0){
            count+=n/5;
            n=n/5;
        }
        return count;
    }       


编辑于 2021-04-16 18:58:01 回复(1)
游骑兵PXZ头像 游骑兵PXZ
要相乘产生0，那肯定是与5相乘的结果。对n!如果分解质因数的话，结果为0的个数只与2与5的个数有关，每一次2*5就能产生一个0。因为2的个数肯定要大于5的个数，所以只要关注5的个数就可以了.

 
    public static long thenumberof0(long n) {
        long res = 0;
        long i = 5;
        while (i<=n){
            res+=n/i;
            i*=5;
        }
        return res;
    }
发表于 2020-11-15 10:55:45 回复(0)
唐氏综合征头像 唐氏综合征
由于因子2出现的个数总是大于因子5出现的个数，因此只需要考虑因子5
只有 2* 5 会出现一个0， 因此就看出现多少个 2* 5, 其中2不用考虑，因此因子5的个数就是能使得结尾有多少个0的关键，直接求出 n 能拆出来多少个因此5就是题解:
    n >= 5*5*5....
转为代码就是看 n 拆出来的5的个数： 

    public long thenumberof0 (long n) {
        // write code here
        long cnt = 0;
        while (n != 0) {
            cnt += n / 5;
            n /= 5;
        }
        return cnt;
    }

这根辗转相除法求两个数的最大公约数原理类似，理解就行
发表于 2024-06-28 17:01:04 回复(0)
Java
牛客839384289号头像 牛客839384289号 
public long thenumberof0 (long n) {
    // write code here
    long res=0;
    while(n!=0){
        res+=n/5;
        n/=5;
    }
    return res;
}

编辑于 2024-03-17 14:16:22 回复(0)
牛客2024007号头像 牛客2024007号
md，头皮想破了才想明白
编辑于 2024-02-03 17:16:54 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def thenumberof0(self , n: int) -> int:
        # write code here
        count = 0 
        while n > 0:
            count += n//5
            n = n//5
        return count

发表于 2022-04-25 15:57:14 回复(0)
Asuna_ysn头像 Asuna_ysn 
typedef long long LL;

class Solution {
public:
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        LL t = 0;
        while(n) n /= 5, t += n;
        return t;
    }
};

发表于 2022-03-22 21:19:26 回复(0)
C++
牛客嗷嗷头像 牛客嗷嗷 
class Solution {
  public:
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        // write code here
        long long sum = 0;
        while (n)
            sum += n /= 5;

        return sum;
    }
};

发表于 2022-03-14 21:42:24 回复(0)
Python 3
mgxjq头像 mgxjq
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# the number of 0
# @param n long长整型 the number
# @return long长整型
#
class Solution:
    def thenumberof0(self , n: int) -> int:
        # write code here
        result = 0
        i = 5
        while n >=i:
            result += n // i
            i *= 5
        return result
发表于 2022-01-24 20:26:26 回复(0)
Java
玄鉴头像 玄鉴 
import java.util.*;


public class Solution {
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    public long thenumberof0 (long n) {
    long count=0;
    while(n!=0){
        count+=n/5;
        n/=5;
    }
    return count;
    }
}
发表于 2022-01-01 12:27:58 回复(0)
C++
比那名居的桃子头像 比那名居的桃子
一行代码： 
class Solution {
public:
    long long thenumberof0(long long n) {
        return n<5?0:n/5+thenumberof0(n/5);
    }
};


发表于 2021-12-31 19:53:25 回复(0)
imleep头像 imleep
发表于 2021-11-17 20:10:18 回复(0)
菜鸡一条头像 菜鸡一条
暴力还想了半天大数该怎么解决的我是憨憨
发表于 2021-08-29 17:15:28 回复(0)
Go
bigkai头像 bigkai
package main

/**
 * the number of 0
 * @param n long长整型 the number
 * @return long长整型
*/
func thenumberof0( n int64 ) int64 {
    var res, i int64 = 0, 5
    for i <= n {
        res += n / i
        i *= 5
    }
    return res
}
发表于 2021-08-14 11:14:51 回复(0)
Python 3
冷风tt头像 冷风tt
分别计算1~n中5的个数，5**2的个数，5**3的个数， ...., 最后结果就是这些个数之和。
class Solution:
    def thenumberof0(self , n ):
        # write code here
        if n < 5:
            return 0
        res = 0
        k = int(math.log(n, 5))
        cur = 5
        for i in range(k):
            res += n // cur
            cur *= 5
        return res
发表于 2021-07-30 17:19:26 回复(1)
Python 3
HHHChen77头像 HHHChen77 
class Solution:
    def thenumberof0(self , n ):
        # 阶乘末尾为0的数量取决于阶乘范围内出现'5'的次数
        # 如 5->1次(5)  25->2次(5*5)  125->3次(5*5*5)
        count = 0
        while n:
            count += (n//5)
            n = n // 5
        # 返回
        return count

发表于 2021-07-27 12:46:50 回复(0)
Java
KaiGG头像 KaiGG
n/5表示在n中有多少个5，也就是n（n-1）...有0的个数，将d执行d*5，这样可以计算出n!中有两位0的个数，这时候也只加一次，因为可能这个数有更多0，继续d*5,计算出有三位0的个数。。。种种加上之后就是n!中有多少0。

public long thenumberof0 (long n) {
        // write code here
        long ans = 0;
        long d = 5;
        while(n>=d)
        {
            ans+=n/d;
            d = d*5;
        }
        return ans;
    }
代码抄的。。。嘻嘻

发表于 2021-05-06 18:45:57 回复(0)
提交观点

问题信息

基础数学
难度：
27条回答 3267浏览

热门推荐

通过挑战的用户

查看代码

相关试题

阶乘末尾0的数量

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号