leetcode-793. 阶乘函数后 K 个零
2022/8/28 23:25:30
本文主要是介绍leetcode-793. 阶乘函数后 K 个零,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
793. 阶乘函数后 K 个零
图床:blogimg/刷题记录/leetcode/793/
刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html
题目
思路
首先我们令\(zeta(x)\)为\(x!\)末尾零的个数。根据172.阶乘后的零有\(zeta(x)=\sum_{k=1}^\infty\left\lfloor\frac{x}{5^k}\right\rfloor\)
记\(n_x\)表示\(x!\)末尾零的个不小于x的最小数,那么题目等价于求解\(n_{k+1}-n_k\)
由于\(zeta(x)\)为单调不减函数,因此\(n_{k+1}\)和\(n_k\)可以通过二分查找来求解。
又因为\(zeta(x)=\sum_{k=1}^\infty\left\lfloor\frac{x}{5^k}\right\rfloor\geq\left\lfloor\frac{x}{5}\right\rfloor\)
得到\(zeta(5x)\geq x\)
所以当二分求解\(n_x\)时,我们可以将二分的初始右边界\(r\)设置为\(5x\)
解法
class Solution { public: int zeta(long x) { int res = 0; while (x) { res += x / 5; x /= 5; } return res; } long long help(int k) { long long r = 5LL * k; long long l = 0; while (l <= r) { long long mid = (l + r) / 2; if (zeta(mid) < k) { l = mid + 1; } else { r = mid - 1; } } return r + 1; } int preimageSizeFZF(int k) { return help(k + 1) - help(k); } };
- 时间复杂度:\(O(log^2k)\),其中\(k\)为题目给定数字,二分查找\(n_{k+1}\),\(n_k\)的时间复杂度为\(O(logk)\),其中每一步计算\(zeta(x)\)的时间复杂度为\(O(logk)\)。
- 空间复杂度:\(O(1)\),\(zeta(x)\)仅使用常量空间
补充
这篇关于leetcode-793. 阶乘函数后 K 个零的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享