#3725. 幸运数字求和
幸运数字求和
题目描述
小明是个幸运数字迷,他喜欢寻找连续的幸运数字之和。给定一个正整数 n,请你计算从1到n之间所有连续幸运数字的和。幸运数字是指该数字的所有位数之和等于该数字本身的数。例如,33是一个幸运数字,因为3+3=6,但33=6不成立,所以33不是幸运数字。
输入格式
一个正整数n(1 <= n <= 100)
输出格式
一个整数,表示从1到n之间所有连续幸运数字的和
样例
10
45
20
45
说明/提示
- 输入保证n在1到100之间
- 请在1秒内完成所有测试用例
解析
题解
解题思路
题目要求计算从1到n之间所有连续幸运数字的和。幸运数字的定义是其所有位数之和等于该数字本身。例如,33不是一个幸运数字,因为3+3=6,但33不等于6。
首先,我们需要一个函数来判断一个数是否为幸运数字。对于每个数字,我们将其每一位数加起来,如果加起来的和等于该数字,则该数字是幸运数字。
然后,我们遍历从1到n之间的所有数字,使用上述函数检查每个数字是否为幸运数字,如果是,则将其加到总和中。
算法选择理由
该算法的时间复杂度主要由判断幸运数字的函数决定。对于每个数字,我们最多需要遍历其每一位数,因此时间复杂度为O(d),其中d为数字的位数。由于输入规模较小(n <= 100),因此该算法在1秒内可以完成所有测试用例。
复杂度分析
- 时间复杂度:O(n * d),其中n为输入范围,d为数字的位数。对于最坏情况,n=100,d=2,因此时间复杂度为O(200)。
- 空间复杂度:O(1),只需要常数级的额外空间。
来源
AI 生成 · 本机Ollama · 入门 · 枚举