Lintcode2TrailingZerossolution题解-创新互联
【题目描述】
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:国际域名空间、网站空间、营销软件、网站建设、若羌网站维护、网站推广。Write an algorithm which computes the number of trailing zeros in n factorial.
设计一个算法,计算出n阶乘中尾部零的个数。
【题目链接】
http://www.lintcode.com/en/problem/trailing-zeros/
【题目解析】
传统解法是首先求出n!,然后计算末尾0的个数。(重复÷10,直到余数非0)该解法在输入的数字稍大时就会导致阶乘得数溢出,不足取。
O(logn)解法:一个更聪明的解法是考虑n!的质数因子。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数,问题就解决了。考虑下面的例子:
n = 5: 5!的质因子中 (2 * 2 * 2 * 3 * 5)包含一个5和三个2。因而后缀0的个数是1。
n = 11: 11!的质因子中(2^8 * 3^4 * 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。
我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢?一个简单的方法是计算floor(n/5)。例如,7!有一个5,10!有两个5。除此之外,还有一件事情要考虑。诸如25,125之类的数字有不止一个5。例如,如果我们考虑28!,我们得到一个额外的5,并且0的总数变成了6。处理这个问题也很简单,首先对n÷5,移除所有的单个5,然后÷25,移除额外的5,以此类推。
【参考答案】
http://www.jiuzhang.com/solutions/trailing-zeros/
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:Lintcode2TrailingZerossolution题解-创新互联
分享URL:http://pwwzsj.com/article/cssjse.html