欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 题目:尾随零

程序员文章站 2022-03-24 17:36:38
...

URL:https://www.lintcode.com/problem/factorial-trailing-zeroes/description

描述

给定一个整数n,返回n!(n的阶乘)的尾随零的个数。

您的解法时间复杂度应为对数级别。

样例

样例1

输入: n = 5
输出: 1
解释:
1*2*3*4*5=120

样例2

输入: n = 10
输出: 2
解释:
1*2*3*4*5*6*7*8*9*10=3628800

思路:

因为结尾处的每一个0就是数中10的个数,10=2*5,所以求出数中包含的5的个数即可(不能是2的个数,因为2这个质因子包含在其他的数之中)。

在代码段中添加:

    long long temp = 5;
            long long count = 0;
            while(temp<=n){
                count+=n/temp;
                temp*=5;
            }
            return count;

即可:

LintCode 题目:尾随零