500万的房子400万卖了，200万又买回来，亏了还是赚了?
程序员老鬼约 4 分钟刚看到个贴子：一网友说，自己当年500万的房子，急用钱400万卖了，最近又花200万买回来，问大家这是亏了还是赚了。
网友回帖挺有意思的，有人算账说：明摆着亏了100万；也有人说：现在等于700万拿下一套房，心疼；还有人说：不急用钱，你哪来那400万度过难关？能平安扛过去就是赚。
我觉得这事吧，纯看你怎么定义“赚亏”。如果只盯着房价，那当然是亏钱；但如果当时那400万帮你顶住了生意周转、家里看病、孩子上学这些事，那这100万就是“过路费”。生活很多时候就像坐地铁，倒一趟车多花了钱，但你安全到站了，这趟就不算亏。
面试题：阶乘函数后 K 个零
昨天晚上快十一点，我在公司楼下等外卖，手机一震，我们组那个小李给我发了个截图—— “哥，阶乘后面 K 个零那个题，你咋写的啊？我写暴力 for 循环算阶乘，直接把服务器风扇干到起飞……”
我当时看了一眼就笑了：这题要是还老老实实算阶乘，本身就已经输了，对吧。
题目大概长这样（表述有出入别纠结哈）：
给一个整数
k，问：有没有一个n，它的阶乘n!的十进制表示最后刚好有 K 个零？ 或者简单点：怎么快速算n!末尾有多少个零？
很多平台会分成两步出：
先写函数 f(n)：返回n!末尾有多少个 0再围绕 “后 K 个零” 玩花样：比如找最小的 n，使得f(n) >= K
你要是这俩都拿下，这道题就彻底拿捏了。
为啥会有“末尾零”？
这个其实特别生活化。十进制里一个末尾 0 就是一个因子 10。 10 = 2 × 5。
n! = 1 * 2 * 3 * ... * n 里面，2 的个数特别多，几乎随便拿一个偶数就带一个 2； 真正稀缺的是 5，所以：
n!末尾零的个数 = 里面因子 5 的个数
比如 10! 里面有多少个 5？
5 提供一个 5 10 再提供一个 5 所以是 2 个 5，对应 10! = 3628800，末尾刚好 2 个 0，完美对上。
但注意一个细节： 像 25 = 5²，这种里面有两个 5，要加 2 次。 所以算法要稍微精细一点。
数 5 的正确姿势
暴力一个个因子拆分肯定不行，会超时。 有个特别巧的小规律：
n / 5：有多少个数能提供至少一个 5（5, 10, 15, …）n / 25：有多少个数能额外再提供一个 5（25, 50, 75, …）n / 125：再额外提供……
所以公式是：
f(n) = n/5 + n/25 + n/125 + ...
一直除到变成 0 为止。 这个复杂度大概是 O(log₅ n)，比起算阶乘本身快太多了。
上点 Java 代码，别光嘴上说
小李最开始写的是那种 BigInteger 疯狂乘，然后 while (x % 10 == 0) 去数 0， 我直接让他删了……
正确写法就几十行：
publicclassFactorialZeros{
// 计算 n! 末尾有多少个 0
publicstaticlongcountTrailingZeros(long n){
long res = 0;
while (n > 0) {
n /= 5; // 每除一次 5，就多一层因子 5
res += n;
}
return res;
}
publicstaticvoidmain(String[] args){
System.out.println(countTrailingZeros(10)); // 2
System.out.println(countTrailingZeros(25)); // 6
}
}
你可以随便在本地跑一下，25! 末尾是 6 个 0，这个很多题解里都爱拿来举例。
那“后 K 个零”这句咋理解？
面试里一般会这么问你其中一种（或者两个一起问）：
已知 n，问n!末尾有多少个 0 —— 直接用countTrailingZeros(n)。已知 K，问：最小的n是多少，使得n!末尾至少有 K 个 0？
第二种就要用到二分了。
为啥能二分？ 因为 f(n) 单调不减：n 越大，阶乘里乘的数越多，5 只会变多不会变少，所以 0 的个数一定是递增的（或者平的）。
所以可以这样搞：
左边
l = 0右边
r = 5 * K足够大了，因为每 5 个数，“大概”多一个 0中间
mid，算f(mid)如果 f(mid) >= K，说明答案在左边，r = mid否则在右边， l = mid + 1最后
l就是最小的那个 n
Java 版写出来大概这样：
publicstaticlongminNForAtLeastKZeros(long k){
long left = 0;
long right = 5 * k + 5; // 多留一点冗余
while (left < right) {
long mid = left + (right - left) / 2;
long zeros = countTrailingZeros(mid);
if (zeros >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // 最小的 n，使得 n! 至少有 k 个 0
}
你要是题目要求的是“恰好 K 个 0”，那就可以：
找出满足 >= K的最小n1再找出满足 > K的最小n2中间 [n1, n2)的这些n，f(n)都等于 K 如果n1 == n2，说明根本没有这样的n。
这个就有点超范围了，面试官一般问到前两个你就已经很香了。
小李那个题，改完代码之后他跟我说一句：“原来数 5 这么简单，我之前从来没往这块想过。”
其实很多算法题都是这样，看上去是“算阶乘”“大数运算”， 真正的解法往往是：先把数学关系想明白，然后代码只是个翻译器。
你要是刷到这道“阶乘函数后 K 个零”， 脑子里先自动弹出来：10 = 2 × 5，2 不缺，数 5 就完了；单调就二分， 基本这题就不用慌了。
行了，先这样，我去把刚刚点的那杯奶茶拿上来，不然等会又被前台大姐顺走了…
-END-
我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html