专栏首页轮子工厂好吧,又是两分钟看完一道投机取巧的算法题

好吧,又是两分钟看完一道投机取巧的算法题

题目描述

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

示例 1:

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

示例 2:

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

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

题目解析

题目很好理解,数阶乘后的数字末尾有多少个零。

最简单粗暴的方法就是先乘完再说,然后一个一个数。

事实上,你在使用暴力破解法的过程中就能发现规律: 这 9 个数字中只有 2(它的倍数) 与 5 (它的倍数)相乘才有 0 出现

所以,现在问题就变成了这个阶乘数中能配 多少对 2 与 5

举个复杂点的例子:

10! = 【 2 *( 2 * 2 )* 5 *( 2 * 3 )*( 2 * 2 * 2 )*( 2 * 5)】

在 10!这个阶乘数中可以匹配两对 2 * 5 ,所以10!末尾有 2 个 0。

可以发现,一个数字进行拆分后 2 的个数肯定是大于 5 的个数的,所以能匹配多少对取决于 5 的个数。(好比现在男女比例悬殊,最多能有多少对异性情侣取决于女生的多少)。

那么问题又变成了 统计阶乘数里有多少个 5 这个因子

需要注意的是,像 25,125 这样的不只含有一个 5 的数字的情况需要考虑进去。

比如 n = 15。那么在 15! 中 有 35 (来自其中的5, 10, 15), 所以计算 n/5 就可以 。

但是比如 n=25,依旧计算 n/5 ,可以得到 55,分别来自其中的5, 10, 15, 20, 25,但是在 25 中其实是包含 25 的,这一点需要注意。

所以除了计算 n/5 , 还要计算 n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5直到商为0,然后求和即可。

代码实现

public class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}

本文分享自微信公众号 - 轮子工厂(Programmer-ing)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我可能早就到阿里腾讯上班去了,如果早点知道这种学编程的方法的话

    最近在学C语言程序设计时总是遇到一些概念上不清晰与混乱的地方,在一次偶然间想到了以前看过的一部电影《我是谁,没有一个系统是安全的》,里面的主角用社会工程学的想法...

    谭庆波
  • 如何大规模拼接字符串?(含中奖名单)

    月初公众号上给大家送了10本书,有5本是用抽奖助手抽的,大家可以在抽奖助手上查看。

    谭庆波
  • Windows装逼操作

    大家应该有在电视/电影里看到这样的一幕:一个戴着墨镜的大神坐在电脑前,神情严肃,手指飞快地在电脑键盘上敲打着,电脑上的命令闪动着,而大神全程都没碰一下鼠标,如下...

    谭庆波
  • 好吧,又是两分钟看完一道投机取巧的算法题

    事实上,你在使用暴力破解法的过程中就能发现规律: 这 9 个数字中只有 2(它的倍数) 与 5 (它的倍数)相乘才有 0 出现。

    五分钟学算法
  • 学小米写出高质量标题

    一个网站的内容的标题写的好,可以促进用户点击,提高pv 减少跳出率,这样对seo是非常有好处的,用户进来后没点其他内容跳出,说明网站内容质量不够好,百度对网站印...

    貟王軍
  • 接力10G,25G将成为数据中心最优解决方案

    随着云计算、大数据、移动互联网和智慧城市的兴起,互联网数据流量呈爆发式增长趋势,运营商急需将现有的数据中心升级到云数据中心,以提供更加灵活的业务和应用支撑。目前...

    易天光通信
  • 腾讯云25端口解封方法教程

    腾讯云25端口默认是关闭的,想要使用25端口邮件服务需要解封25端口,服务器百科网分享开通腾讯云25端口的方法教程:

    上云小秘书
  • 震惊!app为何会突然崩溃???

    Android技术优化日新月异,如今Android 10.0 已经发布,系统性能非常流畅,体验上完全可以媲美iOS;到了各大厂商手里,改源码、自定义系统,使得A...

    程序亦非猿
  • SDN,NFV和SD-WAN携手共进

    网络是一种由大量的协同行为聚集的集合,因此我们所面对的关键网络技术“革命”间存在关联关系也就不足为奇了。然而这些关键网络技术之间的关系却不怎么明朗。软件定义网络...

    SDNLAB
  • SDN&NFV营收大数据分析

    数学公式是简单的:流动性+大数据+物联网+分析意图网络——数据中心、云计算及边缘节点的需求,必须更快的处理工作负载,并且随着当前的技术,IT预估甚至不能解决这些...

    SDNLAB

扫码关注云+社区

领取腾讯云代金券