首页 > 试题广场 >

阶乘末尾0的数量

[编程题]阶乘末尾0的数量
  • 热度指数：11762 时间限制：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
算法知识视频讲解
添加回答
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)
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)
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)
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)
Java
牛客330025463号头像 牛客330025463号
public long thenumberof0 (long n) {
        long count = 0;
        while (n > 0) {
            n = n / 5;
            count += n;
        }
        return count;
    }
发表于 2021-03-28 11:22:52 回复(0)
Java
花落梦里头像 花落梦里 
    public long thenumberof0 (long n) {
        //每次对10取余，然后再/10，再取余
        if(n==0) return 1;
        //结果为0的个数只与2与5的个数有关。因为2的个数肯定要大于5的个数，所以只要关注5的个数就可以了.
        long i=5,count=0;
        while(i<=n){
            count=count+n/i;
            i=i*5;//5有1个5，因此n是5的几倍就有几个5，而n有几个25又多出一个5来
        }
       return count;
    }

}
编辑于 2021-03-27 19:32:57 回复(1)
提交观点

问题信息

基础数学
难度：
6条回答 3289浏览

热门推荐

通过挑战的用户

查看代码

相关试题

阶乘末尾0的数量

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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