Lintcode 尾部的零

xiaoxiao2021-02-28  97

描述: 设计一个算法,计算出n阶乘中尾部零的个数 样例: 11!=33916800,,因此应该返回2 分析: 1.刚拿到题目,直接计算了n!的值,然后溢出了,pass

2.n! = K*10^m,n!=(2^x)*(3^y)*(5^z),10=2*5,所以计算min(2,5),计算5的个数

int count = 0; for(int i = 0;i < n;i++){ int tmp = i; while(n%5 == 0){ count++; tmp = tmp/5; } }

然而,当n足够大的时候,运行时间过长了

3.翻了编程之美,里面有个公式:Z = [n/5]+[n/5^2]+[n/5^3]+···

代码:

public class Solution { /* * @param n: An integer * @return: An integer, denote the number of trailing zeros in n! */ public long trailingZeros(long n) { // write your code here, try to do it without arithmetic operators. long count = 0; while(n!=0){ count += n/5; n=n/5; } return count; } }

转载请注明原文地址: https://www.6miu.com/read-33417.html

最新回复(0)