n 的阶乘尾部零的个数 (lintcode:trailing-z

计算出 n 阶乘中尾部零的个数。
例如11! = 39916800，因此应该返回 2

代码1:

def trailingZeros(n):
  count = 0
  sum1 = 1
  while n:
    sum1 *= n
    n -= 1
  while sum1 % 10 == 0:
    count += 1
    sum1 //= 10 
  return count

print trailingZeros(100)

上面这段代码不能计算太大的数，比如输入1001171717就不行了。

转换另一个思路。

一个数 n 的阶乘末尾有多少个 0 取决于从 1 到 n 的各个数的因子中 2 和 5 的个数。而 2 的个数是远远多余 5 的个数的, 因此求出 5 的个数即可。求解因子 5 的个数的方法是用 n 不断除以 5, 直到结果为 0。

def trailingZeros(n):
  if n < 0:
    return 'Wrong'
  elif n == 0:
    return '1'
  else:
    zero_num = 0
    while n:
      n //= 5
      zero_num += n
    return zero_num

(因子：假如整数 n 除以 m，结果是无余数的整数，那么我们称 m 就是 n 的因子。 需要注意的是，唯有被除数、除数、商皆为整数，余数为零时，此关系才成立。)

lintcode 原题

20171231