首页 > 编程语言(其他) > Leetcode 172 Factorial Trailing Zeroes

Leetcode 172 Factorial Trailing Zeroes

2017年1月11日 发表评论 阅读评论

Given an integern, return the number of trailing zeroes inn!.

Note:Your solution should be in logarithmic time complexity.

求阶乘的后缀0个数

乘法中的零来源于10,10来源于2和5,在阶乘中,一个数的质因子出现一次5,那么必然有其他数的质因子出现若干次2

所以问题变为求解质因子5出现的次数,

n/5求出包含一个5的数字个数

n/25求出包含两个5的数字个数…以此类推

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

作者:u012614906 发表于2017/1/11 15:03:15 原文链接
阅读:154 评论:0 查看评论
分类: 编程语言(其他) 标签: