[每日一题]172. Factorial Trailing Zeroes

经典的数学相关的面试题解法：分解质因素...

题目描述

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

https://leetcode.com/problems/factorial-trailing-zeroes/?tab=Description

题目分析

题意：给定一个正整数 n ，求其阶乘的尾部的 0 的个数。

例子：

给定的 n = 5, 那么 n! = 5 x 4 x 3 x 2 x 1 = 120 , 120 的尾部有 1 个0，所以结果是 1；

给定的 n = 10, 那么 n! = 10x9x8x7x6x5x4x3x2x1=3628800, 3628800 的尾部有 2 个0，所以结果是 2.

容易想到的方案是暴力法：先求 n 的阶乘的值，然后把值转换成字符串，从右到左计算 0 的个数。但是暴力法有两个问题：时间复杂度太高和 n! 阶乘的值有可能特别大（超过 2^31 - 1) 。所以，我们应该寻找更好的方案：数学法。

在介绍数学方法之前，我们先复习一下小学数学的三个基本概念(是时候拿出我们的小学数学课本了)。

合数：一个数如果除了1和它本身以外还能被别的因数整除，这样的数叫做合数
质数：除了1和这个数本身之外还可以被其它自然数整除
分解质因素：一个合数用几个质数相乘的形式表示出来

毫无疑问，n 的阶乘的值 n! 是满足合数的定义的。所以，可以得到这个非常重要的结论：n! 可以表示为若干质数的乘积。归纳成公式如下:

n! = 2^x2 * 3^x3 * 5^x5 * ... * m^xm

m^xm: 表示 m 的 xm 次幂, xm 是正整数

例如： 5! = 2^1 * 3^1 * 4^1 * 5^1 , 所以 x2 = 1 , x5 = 1

得到了这个非常关键的公式后，接下来我们需要证明一个问题：

对于任意可以分解成质因数的正整数，其分解等式一定满足该不等于是: x2 > x5 。

也就是说，2 的次幂一定大于或者等于 5 的次幂。

假设 n 是一个正整数， [n / k] 表示 1 -> n 中能被 k 整除的个数，那么很显然有如下的推论成立

[n/2] > [n/5] ( 2 的步长小于 5 的步长)

[n/4] > [n/25]

…

[n/2^m] > [n/5^m]

随着幂次m的上升，出现2^m的概率会远大于出现5^m的概率。因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂。

回到本题，题意要求 n! 的末尾 0 的个数。由上面的数学公式，我们可以得到等式1：

n! = 2^x2*3^x3*5^x5 ...

进一步推导出等式2

n! = (2*5)^x5 * 2^(x2-x5) * 3^x3 ...

末尾0的个数是由 10(也是 2 x 5) 的个数决定的，10 的个数 = 末尾 0 的个数。由等式2 我们可以得到：10的个数等于 5 的个数。所以，本题我们只需要求出 n! 中 5 出现的次数就可以了。 x5 的值满足如下的等式3:

x5 = [n/5] + [n/5^2] + [n/5^3] + ... + [n/5^14]

等式3 的一个变种等式4:x5 = [n/5] + [(n/5)/5] + [(n/5^2)/5] + ... + [(n/5^13)/5]可以由等式4 写出如下的递归是

f(n) = n/5 + f(n/5)

为什么5的个数最多是 14 ?

因为正整数的取值范围是 2^31 - 1 , 5^15次幂已经超过了正整数的取值的上限。

解题方案

对于“题目分析”中的等式3，我们可以用如下的几种办法实现

递归

有等式4 的递推式，我们实现如下的逻辑