继续优化一下,时间复杂度最低的算法
时间: 2023-08-12 09:28:13 浏览: 58
进一步优化,可以考虑使用数学方法降低时间复杂度。我们可以通过计算位数之和的范围,缩小需要遍历的数字范围。具体来说,我们可以首先计算出a和b的位数之和,然后根据s和a、b的位数之和之间的关系,确定需要遍历的数字范围。例如,如果s的值很小,那么需要遍历的数字范围就很小,可以有效地减少时间复杂度。
代码如下:
```
#include <stdio.h>
int main() {
long long int a, b, s, i, sum, count = 0, min_num = 0;
int bitsuma = 0, bitsumb = 0;
scanf("%lld %lld %lld", &a, &b, &s);
long long int tempa = a, tempb = b;
while (tempa > 0) {
bitsuma += tempa % 10;
tempa /= 10;
}
while (tempb > 0) {
bitsumb += tempb % 10;
tempb /= 10;
}
long long int low = a, high = b;
if (s > bitsumb) {
printf("0\n");
return 0;
}
if (s <= bitsuma) {
high = a + (s - bitsuma) * 9;
} else {
low = b - (bitsumb - s) * 9;
}
for (i = low; i <= high; i++) {
sum = 0;
long long int temp = i;
while (temp > 0) {
sum += temp % 10;
temp /= 10;
}
if (sum == s) {
if (min_num == 0) {
min_num = i;
}
count++;
}
}
printf("%lld\n%lld", count, min_num);
return 0;
}
```
在这个代码中,我们先计算出a和b的位数之和bitsuma和bitsumb,然后根据s和bitsuma、bitsumb之间的关系,确定需要遍历的数字范围。如果s比bitsumb还大,那么显然不存在符合条件的数字,直接输出0即可。如果s比bitsuma小或等于bitsuma,那么需要遍历的数字范围就是[a, a+(s-bitsuma)*9];如果s比bitsumb大,那么需要遍历的数字范围就是[b-(bitsumb-s)*9, b]。这个代码的时间复杂度为O(logb)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)