Leetcode 172. 阶乘后的零

题目描述

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

示例 1:

输入: 3

输出: 0

解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5

输出: 1

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

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

解法

因为偶数与 5 相称结果会产生一个 0,所以阶乘结果末尾 0 的个数,取决于相乘数列中偶数与 5 的个数。因为是递加一的阶乘,所以偶数的个数一定大于 5 的个数,所以阶乘结果尾数中零的数量取决于数列中包含 5 的个数。

从 1 开始,每 5 个数会包含一个 5,每 25 个数,会包含两个 5,每 125 个数,会包含 3 个 5...。所以 n 个数中,包含 5 的个数为 sum=\frac n5+\frac n {5^2}+ ... +\frac n {5^i},n\le 5^i,即sum=\sum_{i=1}^{log_5n} \frac n{5^i}

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret=0
        while n>0:
            ret,n=ret+n//5,n//5
        return ret
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 原文欢迎关注http://blackblog.tech/2018/06/03/LeetCodeReview/欢迎关...
    BlackBlog__阅读 1,986评论 0 9
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2
  • 8月22日-----字符串相关 2-3 个性化消息: 将用户的姓名存到一个变量中,并向该用户显示一条消息。显示的消...
    future_d180阅读 1,001评论 0 1
  • GitHub链接简书链接CSDN链接 题目 给定一个整数 n, 返回 结果尾数中零的个数。示例1 示例2 说明:...
    MaosongRan阅读 448评论 0 0
  • 金学优二年级数学 朱梓烯 VIP一对一反馈 【上课时间】2019.02.22 【上课老师】刘老师 【上课内容】复习...
    巧青阅读 504评论 0 0