阶乘很简单？恕我直言，阶乘相关的面试题你还真不一定懂！

对于如何算 n 的阶乘，只要你知道阶乘的定义，我想你都知道怎么算，但如果在面试中，面试官抛给你一道与阶乘相关，看似简单的算法题，你还真不一定能够给出优雅的答案！本文将分享几道与阶乘相关的案例，且难度递增。

案例一

给定一个整数 N，那么 N 的阶乘 N! 末尾有多少个 0？例如： N = 10，则 N！= 3628800，那么 N! 的末尾有两个0。

有些人心想，这还不简单，直接算出 N！的值，然后用除以 10 来判断多少个 0 就可以了。

有些人则这样想，直接算 N！的值再来除以 10 判断多少个 0 的话肯定会出现溢出问题，于是开始思索：一个数乘以 10 就一定会在末尾产生一个零，于是，我们可以从“哪些数相乘能够得到 10 ”入手。

没错，只有 2 * 5  才会产生 10。

注意，4 * 5 = 20 也能产生 0 啊，不过我们也可以把 20 进行分解啊，20 = 10 * 2。

于是，问题转化为 N! 种能够分解成多少对 2*5，再一步分析会发现，在 N！中能够被 2 整除的数一定比能够被 5 整除的数多，于是问题就转化为求 1…n 这 n 个数中能够被 5 整除的数有多少个，注意，像 25 能够被 5整除两次，所以25是能够产生 2 对 2 * 5滴。有了这个思路，代码如下：

 1int f(int n){
 2    int sum = 0;
 3    for(int i = 1; i <= n; i++){
 4        int j = i;
 5        while(j % 5 == 0){
 6            sum++;
 7            j = j / 5;
 8        }
 9    }
10    return sum;
11}

有些人想出了这个规律，很是得意，然而，这还不是面试官要的答案，大家想一个问题，

当 N = 20 时，1~20 可以产生几个 5 ？答是 4 个，此时有 N / 5 = 4。

当 N = 24 时，1~24 可以产生几个 5 ？答是 4 个，此时有 N / 5 = 4。

当 N = 25 时，1~25 可以产生几个 5？答是 6 个，主要是因为 25 贡献了两个 5，此时有 N / 5 + N / 5^2 = 6。

…

可以发现 产生 5 的个数为 sum = N/5 + N/5^2 + N/5^3+….

于是，最优雅的写法应该是这样：

1int f(int n){
2    int sum = 0;
3    while(n! = 0){
4        sum += n / 5;
5        n = n / 5;
6    }
7}

这时，你就可以自信这把代码扔给面试官了。

案例2

求 N! 的二进制表示中最低位 1 的位置。例如 3！=6，二进制为 1010，所以 最低位 1 的位置在第二位。

没有思路？请仔细想一下这道题与上道题的关系！

仔细想一下，这道题不也是求末尾有多少个 0 吗？你求出了末尾有多少个0自然知道 1 的位置（0的个数加1就是1的位置了），只不过，这道题是求二进制末尾有多少个 0。

由于是二进制，所以每次乘以 2 末尾就会产生一个 0 。

于是，模仿上面一道题，求 N！含有多少个 2 的个数。心想，幸好我做个类似了，于是一波操作猛如虎，一分钟就写出了代码：

1int f(int n){
2    int sum = 0;
3    while(n! = 0){
4        sum += n / 2;
5        n = n / 2;
6    }
7}

面试官：还能在优化吗？

什么鬼？还要在优化？我都 O(logn) 时间复杂度了。

还记得我之前讲解了几道有关位运算的吗？这道题确实可以用位运算来优化，除以 n / 2 == n >> 1。不过位运算的速度快多了，于是，优化后的代码如下：

1int f(int n){
2    int sum = 0;
3    while(n! = 0){
4        n >>= 1;
5        sum += n;
6    }
7}

还能在优化吗？

可以，不过我先不讲，因为我觉得，这已经够快了。后面讲其他题可能会把这道题再拿出来讲。

如果你能写出这样的代码，已经算很牛逼了。

案例三

给你一个数 N，输出 N! 的值。

没错，就是这么简单，直接让你求阶乘的值。

这个时候，你就要小心了，千万别一波操作

1long long sum = 1;
2for(int i = 1; i <= n; i++){
3    sum *= i;
4
5}

一个 for 循环，马上搞定。

因为你不知道 n 的范围，有可能你用 long long 也是会溢出的，所以这个时候应该要问一下面试官有没有限定 n 的范围。

面试官：没有限定！

这下好了，这道阶乘的题，难度顿时上升了，说实话，我敢保证大部分人还真没去实现过。所以，今天我就带大家来实现一下，以防以后真的被问到。结果最熟悉的题顿时不知道怎么下手好。

这个时候，我们就必须用字符串来存放所求的值的，在相乘的时候也是用字符串来相乘，说白了，就是要会求两个大整数相乘。

下面我们先来实现一个求两个大整数相乘的函数。一种比较简单的方法就是，像我们小学那会一样，让个位数与另一个数的其他数相乘，然后让十位数与另一个的其他数相乘，最后在把他们进行相加。

实现代码如下：

 1    public static String mul(String s1, String s2) {
 2        // 先把字符串转化为 字符数组。
 3        char[] c1 = s1.toCharArray();
 4        char[] c2 = s2.toCharArray();
 5        int len = c1.length + c2.length;
 6        // 用来存放两个数的积,字符的初始值为 '\u0000'，也就是 0
 7        char[] c = new char[len];
 8        // 由于大整数的低位是在字符串的末尾，所以我们从末尾遍历来计算
 9        for (int i = c1.length - 1; i >= 0; i--) {
10            int index = len - 1;
11            int res = 0;//用来存放进位
12            for (int j = c2.length - 1; j >= 0; j--) {
13                int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res;
14                res = temp / 10;
15                c[index--] = (char)(temp % 10);
16            }
17            // 每趟乘下来的进位要进行保存。
18            c[index] = (char)res;
19            len--;
20        }
21        // 最后把c中的字符加上 '0'
22        for (int i = 0; i < c.length; i++) {
23            c[i] += '0';
24        }
25        String s = new String(c);
26        // n位数乘以m位数得到积位 (m+n)位数或者(n+m-1)位数
27        // 我们只需要判断c[0]是否为0，为0则把它舍弃。
28        if(c[0] == '0')
29            return s.substring(1);
30        else
31        return s;
32    }

注意，一定要自己实现一遍，一定要自己实现一遍，因为原理简单，但手动实现就不一定那么简单了，容易出现bug。

采用这种方法的话，两个大整数相乘的时间复杂度为 O(n)，其实还有更快的方法，大概时间复杂度是 O(n^1.6)，不过代码有点小复杂，感兴趣的可以阅读这篇文章：漫画：如何实现大整数相乘？,我这里就不展开说了，不然单独这个就可以另起一篇很长的文章了。

知道了两个大整数相乘之后，我们再来算我们的阶乘，就好做了，我们每次相乘的时候，只需要把它当作两个大整数重复乘就可以了。代码如下：

 1    // N 的阶乘
 2    public static String f(int n) {
 3        String s = "1";
 4        Integer t = null;
 5        for (int i = 2; i <= n; i++) {
 6            t = i;
 7            s = 大整数相乘.mul(s,t.toString());
 8        }
 9        return s;
10    }
11
12    // 大整数相乘
13    public static String mul(String s1, String s2) {
14        // 先把字符串转化为 字符数组。
15        char[] c1 = s1.toCharArray();
16        char[] c2 = s2.toCharArray();
17        int len = c1.length + c2.length;
18        // 用来存放两个数的积,字符的初始值为 '\u0000'，也就是 0
19        char[] c = new char[len];
20        // 由于大整数的低位是在字符串的末尾，所以我们从末尾遍历来计算
21        for (int i = c1.length - 1; i >= 0; i--) {
22            int index = len - 1;
23            int res = 0;//用来存放进位
24            for (int j = c2.length - 1; j >= 0; j--) {
25                int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res;
26                res = temp / 10;
27                c[index--] = (char)(temp % 10);
28            }
29            // 每趟乘下来的进位要进行保存。
30            c[index] = (char)res;
31            len--;
32        }
33        // 最后把c中的字符加上 '0'
34        for (int i = 0; i < c.length; i++) {
35            c[i] += '0';
36        }
37        String s = new String(c);
38        // n位数乘以m位数得到积位 (m+n)位数或者(n+m-1)位数
39        // 我们只需要判断c[0]是否为0，为0则把它舍弃。
40        if(c[0] == '0')
41            return s.substring(1);
42        else
43        return s;
44    }

时间复杂度是 O(n^3)。如果要优化的话，主要是在大整数相乘这里进行优化。

总结

是不是觉得，阶乘也没有那么简单了？这三道与阶乘相关的题，应该是比较常见的题吧，今天跟大家分享一波，希望大家有时间的话，自己也用代码实现一下，特别是算 N!。后面会继续跟大家分享一些我觉得不错的算法题以及一些算法技巧，敬请关注。

推荐阅读