C++二分查找算法:阶乘函数后 K 个零

简介: C++二分查找算法:阶乘函数后 K 个零

本文涉及的基础知识点

二分查找算法合集

题目

f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * … * x,且 0! = 1 。

例如, f(3) = 0 ,因为 3! = 6 的末尾没有 0 ;而 f(11) = 2 ,因为 11!= 39916800 末端有 2 个 0 。

给定 k,找出返回能满足 f(x) = k 的非负整数 x 的数量。

示例 1:

输入:k = 0

输出:5

解释:0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

示例 2:

输入:k = 5

输出:0

解释:没有匹配到这样的 x!,符合 k = 5 的条件。

示例 3:

输入: k = 3

输出: 5

参数范围

0 <= k <= 109

分析

时间复杂度

O(logn*log5n)。FirstEqualMore内的循环logn次,GetNum内循环log5N。

0个数

0的个数就是2和5的个数的较小者。5的个数一定不会多余2的个数,所以计算5的个数就可以了。

如果5x<=value,那么2x一定小于value。

除非是0个,否则5的个数一定不会等于2的个数。

令x>0,则5x/2 = 2x+x/2 >2x > x

5个数

初步想法

非25的倍数,5的倍数 +1
非125的倍数,25的倍数 +2
非625的倍数,125的倍数 +3

可以这样想

5的倍数 +1
25的倍数 +1
125的倍数 +1

二分

初:寻找第一个和最后一个x,使得f(x)等于k,两者相减再+1。要特殊处理不存在f(x)等于k。所以改成寻找x1=第一个f(x)大于等于k,x2=第一个f(x)大于k,x2也是第一个f(x)大于等于k+1。

代码

核心代码

class Solution {
public:
int preimageSizeFZF(int k) {
return FirstEqualMore(k + 1) - FirstEqualMore(k);
}
int FirstEqualMore(int k)
{
long long left = -1, right = k * 5LL;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (GetNum(mid) >= k)
{
right = mid;
}
else
{
left = mid;
}
}
return right;
}
long long GetNum(long long llVaue)
{
long long llRet = 0;
long long five = 5;
while (five <= llVaue)
{
llRet += llVaue / five;
five *= 5;
}
return llRet;
}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector> grid;
int res = 0;
{
Solution slu;
res = slu.preimageSizeFZF(0);
Assert(5, res);
}
{
Solution slu;
res = slu.preimageSizeFZF(5);
Assert(0, res);
}
{
Solution slu;
res = slu.preimageSizeFZF(3);
Assert(5, res);
}
//CConsole::Out(res);

}

2023年3月旧代码

如果f(x)等于k,则f(x+1)、f(x+2)、f(x+3)、f(x+4)都等于k。如果不存在f(x)等于k,则结果为0。所以只有两种返回值,5或0。

class Solution {
public:
int preimageSizeFZF(int k) {
int left = 0, right = 1000 * 1000 * 1000 + 1;
while (right > left + 1)
{
int iMid = left + (right - left) / 2;
const int iNum = GetFiveNum(iMid);
if (iNum == k)
{
return 5;
}
else if (iNum < k)
{
left = iMid;
}
else
{
right = iMid;
}
}
return (GetFiveNum(left) == k) ? 5 : 0;
}
//获取[0,iMax*5] 质因数5的个数
int GetFiveNum(int iMax)
{
int iNum = iMax;
int tmp = 5;
while (iMax >= tmp)
{
iNum += iMax / tmp;
tmp *= 5;
}
return iNum;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
1月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
3天前
|
编译器 C++
【C++核心】函数的应用和提高详解
这篇文章详细讲解了C++函数的定义、调用、值传递、常见样式、声明、分文件编写以及函数提高的内容,包括函数默认参数、占位参数、重载等高级用法。
12 3
|
1月前
|
编译器 C++ 容器
【C++】String常见函数用法
【C++】String常见函数用法
16 1
|
1月前
|
C++
c++常见函数及技巧
C++编程中的一些常见函数和技巧,包括生成随机数的方法、制表技巧、获取数字的个位、十位、百位数的方法、字符串命名技巧、避免代码修改错误的技巧、暂停和等待用户信号的技巧、清屏命令、以及避免编译错误和逻辑错误的建议。
19 6
|
1月前
|
存储 C++
c++学习笔记05 函数
C++函数使用的详细学习笔记05,包括函数的基本格式、值传递、函数声明、以及如何在不同文件中组织函数代码的示例和技巧。
28 0
c++学习笔记05 函数
|
1月前
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
1月前
|
算法 C++ 容器
C++标准库中copy算法的使用
C++标准库中copy算法的使用
17 1
|
2月前
|
C++ 运维
开发与运维函数问题之析构函数在C++类中起什么作用如何解决
开发与运维函数问题之析构函数在C++类中起什么作用如何解决
37 11
|
2月前
|
C++ 运维
开发与运维函数问题之C++类的简单示例如何解决
开发与运维函数问题之C++类的简单示例如何解决
53 10
|
1月前
|
存储 C++
【C/C++学习笔记】string 类型的输入操作符和 getline 函数分别如何处理空白字符
【C/C++学习笔记】string 类型的输入操作符和 getline 函数分别如何处理空白字符
31 0